不明白这题为啥能评黑，也就蓝的水平？（估计很快就掉了吧）
前置知识
- 倍增求LCA
- 树的直径
- 找性质
Solution
新增加的两个点其实是一个样的（深度相同，祖先相同）
考虑新增的一个点 (x) 对答案的贡献。
设先前树上直径的两端点为 (rt1, rt2)。
想一下，如果 (x) 能作为直径一端的点，那另一端要么是 (rt1)，要么是 (rt2)。（别的点只会更劣）
这样就好做了，判断一下 (x) 到这两个端点的距离，如果更大就更新两个端点和直径。
树上两点间距离可以用 (dep_u +dep_v - 2dep_{lca}) 这个公式。
求 (lca) 可以用树上倍增维护。
总复杂度 (mathcal O(20m))，(20) 是倍增的常数。
然后就做完了。
就这？
Code
/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl
using namespace std;
const int MAXN = 1e6+5;
const int INF = 1e9+7;
const int lps = 1e9+7;
int n, m, rt1, rt2, len;
int dep[MAXN];
int fa[MAXN][22];
int read(){
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
return f ? -s : s;
}
int Get_LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
for(int i = 20; i >= 0; --i) {
if(dep[fa[x][i]] < dep[y]) continue;
x = fa[x][i];
}
if(x == y) return x;
for(int i = 20; i >= 0; --i) {
if(fa[x][i] == fa[y][i]) continue;
x = fa[x][i], y = fa[y][i];
}
return fa[x][0];
}
int main()
{
fa[1][0] = 0;
fa[2][0] = 1, fa[3][0] = 1, fa[4][0] = 1;
fa[2][1] = 0, fa[3][1] = 0, fa[4][1] = 0;
dep[1] = 1, dep[2] = dep[3] = dep[4] = 2;
rt1 = 2, rt2 = 3, len = 2, n = 4;
m = read();
for(int i = 1, u; i <= m; ++i) {
u = read();
fa[++n][0] = u, dep[n] = dep[u] + 1;
fa[++n][0] = u, dep[n] = dep[u] + 1;
for(int j = 1; j <= 20; ++j) {
fa[n][j] = fa[fa[n][j - 1]][j - 1];
fa[n - 1][j] = fa[fa[n - 1][j - 1]][j - 1];
}
int lca1 = Get_LCA(n, rt1), lca2 = Get_LCA(n, rt2);
int len1 = dep[n] + dep[rt1] - 2 * dep[lca1];
int len2 = dep[n] + dep[rt2] - 2 * dep[lca2];
if(len1 > len) {
len = len1;
rt2 = n;
}
if(len2 > len) {
len = len2;
rt1 = n;
}
printf("%d
", len);
}
return 0;
}