[Usaco2018 Feb] New Barns

[题目链接]

        https://www.lydsy.com/JudgeOnline/problem.php?id=5192

[算法]

        维护树的直径，在树上离一个点最远的点一定是一条直径的端点。

        在直径为(x , y)的树上加入一个叶子结点z，则新的直径必然为(x , y) , (x , z) , (y , z)中的一条 , 问题转化为询问树上两点距离 ， 倍增即可 ， 时间复杂度 ：O(MlogN)

[代码]

#include
using namespace std;
const int MAXN = 1e5 + 10;
const int MAXLOG = 20;

int n , total , k;
int depth[MAXN] , x[MAXN] , y[MAXN] , belong[MAXN];
int anc[MAXN][MAXLOG];
char op[5];

template  inline void chkmax(T &x,T y) { x = max(x,y); }
template  inline void chkmin(T &x,T y) { x = min(x,y); }
template  inline void read(T &x)
{
    T f = 1; x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
    x *= f;
}
inline int lca(int u,int v)
{
        if (depth[u] > depth[v]) swap(u , v);
        for (int i = MAXLOG - 1; i >= 0; i--)
        {
                if (depth[anc[v][i]] >= depth[u])
                        v = anc[v][i];
        }
        if (u == v) return u;
        for (int i = MAXLOG - 1; i >= 0; i--)
        {
                if (anc[u][i] != anc[v][i])
                        u = anc[u][i] , v = anc[v][i];
        }
        return anc[u][0];
}
inline int dist(int x,int y)
{
        return depth[x] + depth[y] - 2 * depth[lca(x , y)];
}
inline void update(int u)
{
        int tmp = belong[u];
        int nx , ny , nd;
        if (dist(u , x[tmp]) > dist(u , y[tmp]))
        {
                nd = dist(u , x[tmp]);
                nx = u; 
                ny = x[tmp];
        }    else
        {
                nd = dist(u , y[tmp]);
                nx = u;
                ny = y[tmp];
        }
        if (nd > dist(x[tmp] , y[tmp]))
        {
                x[tmp] = nx;
                y[tmp] = ny;
        }
}
inline int query(int k)
{
        int tmp = belong[k];
        return max(dist(k , x[tmp]) , dist(k , y[tmp])); 
}
 
int main()
{
        
        int Q;
        scanf("%d",&Q);
        while (Q--)
        {
                scanf("%s%d",&op , &k);
                if (op[0] == 'B')
                {
                        ++n;
                        if (k == -1)
                        {
                                belong[n] = ++total;
                                anc[n][0] = 0;
                                depth[n] = 1;    
                                x[total] = y[total] = n;
                        } else
                        {
                                depth[n] = depth[k] + 1;
                                anc[n][0] = k;
                                for (int i = 1; i < MAXLOG; i++)
                                        anc[n][i] = anc[anc[n][i - 1]][i - 1];
                                belong[n] = belong[k];
                        }
                        update(n);
                } else printf("%d\n",query(k));
        }
        
        return 0;
    
}