题意:

给你个节点

每次向里面加一个点以及这个点连一条边到一个已知点

每次操作后求树的直径(即两点的距离的最大值)

这一题

我们考虑一个离根最远的点

它dfs一遍得到的所有点的最远点就是答案

所以我们维护这个最远点

如果某个点更远,那么就把它改为最远点,同时我们认定,直径+1

(这里直径+1可以理解为,本身某个点更远,那么它的父亲肯定在一条最长链上,那么

否则,求它和最远点的距离

这可以写个LCA

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int depth[200005];
int up[200005][25];
int father[200005];
int lca(int x,int y)
{
    if (depth[x]<depth[y]) swap(x,y);
    int t=depth[x]-depth[y];
    int i;
    for (i=0;i<20;i++)
    {
        if ((1<<i)&t) x=up[x][i];
    }
    for (i=19;i>=0;i--)
    {
        if (up[x][i]==up[y][i]) continue;
        x=up[x][i];
        y=up[y][i];
    }
    return father[x];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    int farest_point=0;
    int farest_depth=0;
    int ans=0;
    for (i=0;i<20;i++)
    {
        up[0][i]=-1;
    }
    for (i=1;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        x--;
        father[i]=x;
        depth[i]=depth[x]+1;
        int j;
        up[i][0]=x;
        for (j=1;j<20;j++)
        {
            if (up[i][j-1]==-1)
            {
                up[i][j]=-1;
            }
            else
            {
                up[i][j]=up[up[i][j-1]][j-1];
            }
        }
        if (depth[i]>farest_depth)
        {
            farest_point=i;
            ans++;
            farest_depth++;
            printf("%d ",ans);
            continue;
        }
        int t=lca(i,farest_point);
        if (depth[i]-depth[t]+farest_depth-depth[t]>ans)
        {
            ans++;
        }
        printf("%d ",ans);
    }
    return 0;
}