CodeForces_GoodBye 2013_F New Year Tree LCA问题

题意：在一棵树上每次在一个节点上增加两个子节点，问每次更新后树上的最长的一条链是多少。

设最长链的长度为len，链的两个端点为e1,e2，每次增加点的编号为a1,a2。

开始时，显然有len = 2,且可以有 e1 = 2,e2  = 3。

每次通过判断a1与e1,e2之间的较长的一段是否大于len，若不大于则无需更新。

若大于则更新相应节点，若较长一段为a1与e1,则令e2 = a1,否则 令 e1 = a1。

因为a1,a2的父节点相同，所以比较其中一个即可。

计算一条链的长度，设一条链的端点为 u , v ，则其长度必有 len = depth(u) + depth(v) - 2*depth(LCA(u,v)); 

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>

#pragma comment(linker, "/STACK:1024000000");
#define LL long long int

using namespace std;

const int MAXN = 2000110;

struct N
{
    int v;
    N *next;
}*head[MAXN];

N *creat()
{
    N *p = (N *)malloc(sizeof(N));
    p->next = NULL;
    return p;
}

void link(int u,int v)
{
    N *p = creat();
    p->v = v;
    p->next = head[u]->next;
    head[u]->next = p;
}

int point[2*MAXN],r[MAXN],depth[MAXN];
bool mark[MAXN];

int Max_Size;

void dfs(int T,int h)
{
    if(mark[T] == false)
    {
        mark[T] = true;
        r[T] = Max_Size;

        depth[T] = h;
 
        point[Max_Size++] = T;

        for(N *p = head[T]->next; p != NULL; p = p->next)
        {
            if(mark[p->v] == false)
            {
                dfs(p->v,h+1);
                point[Max_Size++] = T;
            }
        }
    }
}

struct ST
{
    int h,v;
}st[4*MAXN];

void Init_St(int site,int l,int r)
{
    if(l == r)
    {
        st[site].v = point[l];
        st[site].h = depth[point[l]];
        return ;
    }

    int mid = (l+r)>>1;

    Init_St(site<<1,l,mid);
    Init_St(site<<1|1,mid+1,r);
    
    if(st[site<<1].h < st[site<<1|1].h)
        st[site] = st[site<<1];
    else st[site] = st[site<<1|1];
}

ST Query_Ancestor(int site,int L,int R,int l,int r)
{
    if(L == l && R == r)
    {
        return st[site];
    }

    int mid = (L+R)>>1;

    if(r <= mid)
    {
        return Query_Ancestor(site<<1,L,mid,l,r);
    }
    if(mid < l)
    {
        return Query_Ancestor(site<<1|1,mid+1,R,l,r);
    }

    ST a1,a2;

    a1 = Query_Ancestor(site<<1,L,mid,l,mid);
    a2 = Query_Ancestor(site<<1|1,mid+1,R,mid+1,r);

    if(a1.h < a2.h)
        return a1;
    return a2;
}

int main()
{
    int i,n,u,m,top,q;
    ST anc;

    scanf("%d",&q);
    
    memset(mark,false,sizeof(bool)*(n+2));
    
    n = q*2+10;

    for(i = 1; i <= n; ++i)
    {
        head[i] = creat();
    }

    link(1,2);
    link(1,3);
    link(1,4);
    link(2,1);
    link(3,1);
    link(4,1);

    top = 5;

    for(i = 0; i < q; ++i)
    {
        scanf("%d",&u);
        link(u,top);
        link(top,u);

        top++;

        link(u,top);
        link(top,u);

        top++;
    }

    Max_Size = 1;
    dfs(1,1);

    Init_St(1,1,Max_Size-1);

    int e1 = 2,e2 = 3,Max_Diameter = 2,Temp_Diameter1,Temp_Diameter2;

    for(i = 1;i <= q; ++i)
    {
        u = i*2+4;
        if(r[u] < r[e1])
        {
            anc = Query_Ancestor(1,1,Max_Size-1,r[u],r[e1]);
        }
        else
        {
            anc = Query_Ancestor(1,1,Max_Size-1,r[e1],r[u]);
        }

        Temp_Diameter1 = depth[u] + depth[e1] - anc.h*2;
     
        if(r[u] < r[e2])
        {
            anc = Query_Ancestor(1,1,Max_Size-1,r[u],r[e2]);
        }
        else
        {
            anc = Query_Ancestor(1,1,Max_Size-1,r[e2],r[u]);
        }

        Temp_Diameter2 = depth[u] + depth[e2] - anc.h*2;

        if(Temp_Diameter1 >= Temp_Diameter2 && Temp_Diameter1 > Max_Diameter)
        {
            Max_Diameter = Temp_Diameter1;
            e2 = u;
        }
        else if(Temp_Diameter2 >= Temp_Diameter1 && Temp_Diameter2 > Max_Diameter)
        {
            Max_Diameter = Temp_Diameter2;
            e1 = u;
        }
        printf("%d\n",Max_Diameter);
    }
    return 0;
}