zcmimi's blog
查看原题

点击跳转

每次给一个叶子节点添加两个儿子,而这个叶子节点能到达的最远的点,也就是上一次求得的直径的两个端点之一

那么每添加一个点更新改点,比较直径与该点到之前直径两端的距离即可

#include<bits/stdc++.h>
const int N=1000011;
int q,cnt=1,d[N],A=2,B=3,R=2,f[21][N];
void swap(int&x,int&y){int t=x;x=y;y=t;}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    for(int k=20;~k;--k)
        if(d[f[k][x]]>=d[y])x=f[k][x];
    if(x==y)return y;
    for(int k=20;~k;--k)
        if(f[k][x]!=f[k][y])
            x=f[k][x],y=f[k][y];
    return f[0][x];
}
int dis(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
int ne(int x){
    d[++cnt]=d[x]+1;f[0][cnt]=x;
    for(int i=1;i<=20;++i)
        f[i][cnt]=f[i-1][f[i-1][cnt]];
    return cnt;
}
void work(int x){
    int Ax=dis(A,x),Bx=dis(B,x);
    if(Ax>R)R=Ax,B=x;
    if(Bx>R)R=Bx,A=x;
}
int main(){
    scanf("%d",&q);
    ne(1),ne(1),ne(1);
    int x;
    while(q--){
        scanf("%d",&x);
        work(ne(x)),work(ne(x));
        printf("%d\n",R);
    }
}
LG CF379F New Year Tree
comment评论
Search
search