CF379F New Year Tree

Description

有一棵树，初始时只有 $4$ 个节点， $2\ 3\ 4$ 的父节点都是 $1$ 。 $q$ 次操作，每次给定一个点 $u$ 。设操作前点数为 $n$ ，那么本次操作就是将 $n+1$ 和 $n+2$ 连在 $u$ 上。操作后输出目前树的直径大小。

$q\leq 5\times 10^5$ 。

Solution

考虑直径的如下性质：

对于树上的任意一点 $u$ ，距离 $u$ 最远的点必然是直径的一个端点。

假设操作前直径的两个端点分别是 $A$ 和 $B$ ，新加的点挂在 $u$ 上，目前点数为 $n$ 。
可以知道距离 $u$ 最远的点一定是 $A$ 或 $B$ ，所以距离 $n+1$ 最远的点也一定是 $A$ 或 $B$ （直径至少为 $2$ ），意思就是 $A$ 和 $B$ 中至少有一个点是直径的端点。另一个点只有可能是原直径的另一端或者 $n+1$ 。而我们是可以动态维护距离的，故取三个距离拿出来暴力判断就可以了。

mark 这个题在这里是因为它通过一条人尽皆知的性质实现了在只有加点操作的情况下动态维护树直径。没准是一些难题的突破口，希望自己可以记住这个 trick 。
这个 trick 可以与重心加一个点至多移动一条边的性质一起记住，都是在动态加点的情况下高效维护。

Code

const int N=1e6+2333;
using namespace std;
int m;
int dep[N],f[N][25];
int LCA(int x,int y){
    if(dep[x]<dep[y]) x^=y^=x^=y;
    for(int i=20;i>=0;--i)
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=20;i>=0;--i)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int dis(int a,int b){return dep[a]+dep[b]-dep[LCA(a,b)]*2;}
int main(){

    r(m);
    int n=4,u=2,v=3,nowdis=2;
    for(int i=2;i<=4;++i) f[i][0]=1,dep[i]=1;
    while(m--){
        int x;r(x);
        dep[n+1]=dep[x]+1,f[n+1][0]=x;
        dep[n+2]=dep[x]+1,f[n+2][0]=x;
        for(int i=0;f[n+1][i];++i) f[n+1][i+1]=f[f[n+1][i]][i];
        for(int i=0;f[n+2][i];++i) f[n+2][i+1]=f[f[n+2][i]][i];
        n+=2;
        int a=dis(u,n),b=dis(v,n),c=nowdis;
        nowdis=max(max(a,b),c);
        if(nowdis==a) v=n;
        else if(nowdis==b) u=n;
        w(nowdis);
    }
    return 0;
}