我们假设当前的直径两端为A, B， 那么现在加入v的两个儿子x, y。
求直径的话我们可以第一次dfs找到最远点这个点必定为直径上的点， 然而用这个点第二次dfs找到最远点， 这两个点就是直径。
因为A, B现在是直径的两端， 那么从v点dfs找到的最远点必定为A或者B， 那么从 x dfs找到的最远点也必定为A或者B， 那么如果有
新的直径其中一个端点不会变， 当前图和原图的差别就是x和y， 那么比较dist(A, x)， dist(B, x)和未加入前直径的长度就能得到当前的直径。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std; const int N = 1e6 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; int f[N][], depth[N];
int q; int getLca(int u, int v) {
if(depth[u] < depth[v]) swap(u, v);
for(int i = ; i >= ; i--)
if(depth[f[u][i]] >= depth[v])
u = f[u][i];
if(u == v) return u;
for(int i = ; i >= ; i--)
if(f[u][i] != f[v][i])
u = f[u][i], v = f[v][i];
return f[u][];
} int dist(int u, int v) {
int lca = getLca(u, v);
return depth[u] + depth[v] - * depth[lca];
} int main() {
depth[] = ;
depth[] = depth[] = depth[] = ;
f[][] = f[][] = f[][] = ;
int A = , B = , dia = , n = ;
scanf("%d", &q);
while(q--) {
int v; scanf("%d", &v);
depth[n + ] = depth[v] + ;
depth[n + ] = depth[v] + ;
f[n + ][] = f[n + ][] = v;
for(int i = ; i < ; i++) {
f[n + ][i] = f[f[n + ][i - ]][i - ];
f[n + ][i] = f[f[n + ][i - ]][i - ];
}
int d1 = dist(A, n + );
int d2 = dist(B, n + );
if(d1 > dia) dia = d1, B = n + ;
else if(d2 > dia) dia = d2, A = n + ;
printf("%d\n", dia);
n += ;
}
return ;
} /*
*/