传送门

$\quad$在得到结论之后，考虑这样一种情况。假设$(s , t )$是原树的某一直径，当新增节点$\{x , y \} $ 以后，假如$\{x,y\}$有可能更新结果的话，那么意味着$\{x , y\}$均可以作为新的直径的一端。

$\quad$那么我们从$s$出发来考虑距离其最远的点，有定理可知，该点一定为树的直径的一端。首先对于原来的树直径$(s , t)$而言，假设新的树直径被更新为$(x , z)$。由定理可知，距离$s$的最远点，要么应该是$x$要么应该是$z$，假如是$x$，由于$(s , t)$是原树的直径，那么此时$s$到$x$的父节点$v$的距离$(s , v) = (s , t )$。即此时树的直径为$(s , t) + 1$。

$\quad$假如距离$s$的最远点为$z(非x , y , s , t的其他点)$，则说明$(s , x) < (s , t)$，即$z$应为原树中距离$s$的最远点，那么就是说$z$就是$t$，那么此时树的直径就是$(t , x)$。

$\quad$最后总结下，也就是树的直径可以表示成$max(\{ (s , t ) (s , x) ( t , x)\}$

Code

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong() 
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int dep[N], fa[N][30];
int lca(int x , int y )
{
  if(dep[x] < dep[y])swap( x , y);

  for(int k = 20 ; k >= 0 ; k --)
   if(dep[fa[x][k]] >= dep[y])x = fa[x][k];

  if(x == y)return x;

  for(int k = 20 ; k >= 0 ; k--)
   if(fa[x][k] != fa[y][k])x = fa[x][k] , y = fa[y][k];

  return fa[x][0];
}
int dis(int x , int y )
{
  int anc = lca(x , y );
  return dep[x] + dep[y] - 2*dep[anc];
}
void solve()
{
   //dep[x] - dep[lca] + dep[y] - dep[lca] + 1
   //dep[x] + dep[y] - 2*dep[lca] + 1
   int q; cin>>q;
   int res = 5;
   dep[1] = 1 , dep[2] = 2 , dep[3] = 2 , dep[4] = 2;
   int s = 2 , t = 3;
   for(int k = 0 ; k <= 20 ; k++)fa[2][k] = fa[3][k] = fa[4][k] = 1;

   int ans = 2;

   for(int i = 1 ; i <= q ; i++)
   {
       int v ; cin>>v;

       int x = res++ , y = res++;
       dep[x] = dep[y] = dep[v] + 1;
       fa[x][0] = fa[y][0] = v;
       for(int k = 1 ; k <= 20 ; k ++)fa[x][k] = fa[y][k] = fa[fa[x][ k - 1]][k - 1];

    //   cout<<dis(s , t)<<' '<<dis(x , s)<< ' '<<dis(x , t)<<endl;
       if(dis(x , s) > dis(s , t))
       {
         ans = dis(x , s);
         t = x;
       }else if(dis(x , t) > dis(s , t))
       {
         ans = dis(x , t);
         s = x;
       }
       cout<<ans<<endl;
   }
   return ;
}
signed main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        solve();
        return 0;
}