CodeForces 379F 树的直径 New Year Tree

题意：每次操作新加两个叶子节点，每次操作完以后询问树的直径。

维护树的直径的两个端点U，V，每次计算一下新加进来的叶子节点到U，V两点的距离，如果有更长的就更新。

因为根据树的直径的求法，若出现新的直径，一定是到U或者到V距离最远。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 const int maxn =  + ;

 const int logmaxn = ;

 int n, Q;

 int L[maxn];

 int fa[maxn];

 int anc[maxn][logmaxn];

 void add(int u, int pa)

 {

     fa[u] = pa;

     L[u] = L[pa] + ;

     anc[u][] = pa;

     for(int j = ; ( << j) < n; j++) if(anc[u][j-])

         anc[u][j] = anc[anc[u][j-]][j-];

 }

 int LCA(int p, int q)

 {

     if(L[p] < L[q]) std::swap(p, q);

     int log;

     for(log = ; ( << log) <= L[p]; log++); log--;

     for(int i = log; i >= ; i--)

         if(L[p] - ( << i) >= L[q]) p = anc[p][i];

     if(p == q) return p;

     for(int i = log; i >= ; i--)

         if(anc[p][i] && anc[p][i] != anc[q][i])

             p = anc[p][i], q = anc[q][i];

     return fa[p];

 }

 int distance(int u, int v)

 {

     int l = LCA(u, v);

     return L[u] + L[v] - L[l] * ;

 }

 int main()

 {

     scanf("%d", &Q);

     n = ;

     fa[] = fa[] = fa[] = ;

     L[] = L[] = L[] = ;

     anc[][] = anc[][] = anc[][] = ;

     int U = , V = , diameter = ;

     while(Q--)

     {

         int p; scanf("%d", &p);

         add(++n, p);

         add(++n, p);

         int l1 = distance(n, U), l2 = distance(n, V);

         if(l1 >= l2 && l1 >= diameter)

         {

             V = n;

             diameter = l1;

         }

         else if(l2 >= l1 && l2 >= diameter)

         {

             U = n;

             diameter = l2;

         }

         printf("%d\n", diameter);

     }

     return ;

 }

代码君