感觉 *3100 有点略高了啊。
题意：太困难了，我说不明白。
做法：
首先先来判一些无解情况，如果有点的度数 \(>3\) 那么完蛋了，怎么做都不可能。
然后考虑根，根的度数要小于等于 \(2\)，然后答案就是离根最远的点的距离 \(+1\)。根据经典结论，这个点一定是直径的两个端点之一，所以我们先要维护动态直径，直接每次加点的时候更新一下直径就可以了。
但是有个问题，我们现在要求的是一个点距离最远的点得到距离最小，如果我只维护直径端点，有可能变化量过大，其实不是很好维护，要更新很多。我们注意到直径中点每次最多移动 \(0.5\)，所以我们考虑在维护直径的同时考虑维护点对 \((x,y)\)，当 \(x=y\) 的时候，直径中点为 \(x\)，否则直径中点在 \((x,y)\) 这条边中间，我们同时维护所有点到直径中点的最短距离。
当 \((x,y)\) 改变的时候，分讨一下，发现会是一个子树/子树补全体 \(\pm1\)，直接用线段树维护即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 5, inf = 2e9;
struct Segtree {int tr[maxn << 2], tag[maxn << 2];void pushup(int t) {tr[t] = min(tr[t << 1], tr[t << 1 | 1]);}void addtag(int t, int val) {tr[t] += val, tag[t] += val;}void pushdown(int t) {addtag(t << 1, tag[t]);addtag(t << 1 | 1, tag[t]);tag[t] = 0;}void build(int l, int r, int t) {tr[t] = inf, tag[t] = 0;if(l == r)return ;int mid = l + r >> 1;build(l, mid, t << 1), build(mid + 1, r, t << 1 | 1);}void modify(int l, int r, int pos, int t, int val) {if(l == r) {tr[t] = val;return ;}int mid = l + r >> 1;pushdown(t);if(pos <= mid)modify(l, mid, pos, t << 1, val);elsemodify(mid + 1, r, pos, t << 1 | 1, val);pushup(t);// cout << l << " " << r << " adsfdf" << tr[t] << " " << tr[t << 1] << " " << val << endl;}void update(int l, int r, int x, int y, int t, int val) {if(x > y)return ;if(x <= l && r <= y) {addtag(t, val); return ;}int mid = l + r >> 1;pushdown(t);if(x <= mid)update(l, mid, x, y, t << 1, val);if(mid < y)update(mid + 1, r, x, y, t << 1 | 1, val);pushup(t);}
} tree;
vector<int> e[maxn];
int f[maxn][21], dep[maxn], dfn[maxn], sz[maxn], tot, n, p[maxn];
void dfs(int u, int fa) {dep[u] = dep[fa] + 1; f[u][0] = fa;dfn[u] = ++tot, sz[u] = 1;for (int i = 0; i < e[u].size(); i++) {int v = e[u][i];if(v == fa)continue;dfs(v, u);sz[u] += sz[v];}
}
void prepare() {for (int j = 1; j <= 20; j++)for (int i = 1; i <= n; i++)f[i][j] = f[f[i][j - 1]][j - 1];
}
int lca(int x, int y) {if(dep[x] < dep[y])swap(x, y);for (int i = 20; i >= 0; i--)if(dep[f[x][i]] >= dep[y])x = f[x][i];for (int i = 20; i >= 0; i--)if(f[x][i] != f[y][i])x = f[x][i], y = f[y][i];return (x == y ? x : f[x][0]);
}
int dis(int x, int y) {return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
int kth_lca(int x, int k) {for (int i = 20; i >= 0; i--)if(k >= (1 << i))k -= (1 << i), x = f[x][i];return x;
}
bool chkin(int x, int y) {return dfn[x] <= dfn[y] && dfn[y] <= dfn[x] + sz[x] - 1;
}
int get_nxt(int x, int y) {if(chkin(x, y))return kth_lca(y, dep[y] - dep[x] - 1);return f[x][0];
}
int deg[maxn];
void solve() {cin >> n;for (int i = 1; i <= n; i++)e[i].clear(), deg[i] = 0;tot = 0;for (int i = 2; i <= n; i++)cin >> p[i], e[p[i]].push_back(i);dfs(1, 0);prepare();tree.build(1, n, 1);tree.modify(1, n, dfn[1], 1, 0);int x = 1, y = 1, u = 1, v = 1;cout << 1 << " ";for (int i = 2; i <= n; i++) {deg[p[i]]++, deg[i]++;// cout << tree.tr[1] << " ";tree.modify(1, n, dfn[i], 1, min(dis(i, x), dis(i, y)));if(deg[p[i]] > 3) {for (int j = i; j <= n; j++)cout << -1 << " ";cout << endl;return ;}if(deg[p[i]] == 3)tree.modify(1, n, dfn[p[i]], 1, inf);if(dis(u, i) < dis(v, i))swap(u, v), swap(x, y);if(dis(u, i) > dis(u, v)) {if(x != y) {if(f[x][0] == y)tree.update(1, n, dfn[x], dfn[x] + sz[x] - 1, 1, 1);elsetree.update(1, n, 1, dfn[y] - 1, 1, 1),tree.update(1, n, dfn[y] + sz[y], n, 1, 1);x = y;}else {// cout << y << " " << get_nxt(i, y) << " " << chkin(y, i) << " " << f[y][0] << endl;y = get_nxt(y, i);// cout << y << "asfsadf" << " " << tree.tr[4] << endl;if(f[y][0] == x)tree.update(1, n, dfn[y], dfn[y] + sz[y] - 1, 1, -1);elsetree.update(1, n, 1, dfn[x] - 1, 1, -1), tree.update(1, n, dfn[x] + sz[x], n, 1, -1);}v = i;}// cout << u << " " << v << " " << i << " " << x << " " << y << endl;cout << tree.tr[1] + (dis(u, v) + 1) / 2 + 1 << " ";// cout << endl;}cout << endl;
}
signed main() {int T; cin >> T;while(T--)solve();return 0;
}
/*
1
8
1 1 2 4 3 6 6
*/