Two Centroids
先考虑对于一棵树，至少要加多少个点才能有两个重心。
以重心为根，设最大儿子的子树大小为 \(mx\)，那么答案就为 \((n - mx) - mx = n - 2mx\)。
接下来考虑如何在加点时维护最大子树，一个显然的性质，加一个点重心最多偏移一位，如果重心偏移，那么 \(mx = \lfloor \frac{n}{2} \rfloor\)。所以我们可以每次加一个点，用倍增寻找其的子树的根，在动态的查询子树大小来更新 \(mx\)，用树状数组根据出现时间计数即可，时间复杂度为 \(O(n \log n)\)。
Code
#include<bits/stdc++.h>
#define LL long long
#define eb emplace_back
#define IN inline
using namespace std;
const int N = 5e5 + 5;
int n;
IN int read() {
int t = 0,res = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) t |= (ch == '-');
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return t ? -res : res;
}
int g[N], dfn[N], dfc, dep[N], f[N][22], siz[N];
vector<int> E[N];
int lowbit(int x){return x & -x;}
void add(int x, int v) {
for (; x <= n; x += lowbit(x)) g[x] += v;
}
int query(int x) {
int res = 0;
for (; x; x -= lowbit(x)) res += g[x];
return res;
}
void dfs(int u, int fa) {
dfn[u] = ++dfc, dep[u] = dep[fa] + 1, f[u][0] = fa, siz[u] = 1;
for (int i = 1; i <= 20; i++)
if (f[u][i - 1]) f[u][i] = f[f[u][i - 1]][i - 1];
else break;
for (auto v : E[u]) dfs(v, u), siz[u] += siz[v];
}
int find(int rt, int x) {
int tmp = dep[x] - dep[rt] - 1;
if (tmp < 0) return -1;
for (int i = 0; tmp; tmp >>= 1, i++)
if (tmp & 1) x = f[x][i];
if (f[x][0] == rt) return x;
return -1;
}
int main() {
for (int T = read(); T; T--) {
n = read(), dfc = 0;
for (int i = 1; i <= n; i++) {
E[i].clear();
for (int j = 0; j <= 20; j++) f[i][j] = 0;
}
for (int i = 2, q; i <= n; i++) q = read(), E[q].eb(i);
dfs(1, 1); int rt = 1, mx = 0;
add(dfn[1], 1);
for (int i = 2; i <= n; i++) {
add(dfn[i], 1);
int x = find(rt, i);
if (x != -1) {
int s = query(dfn[x] + siz[x] - 1) - query(dfn[x] - 1);
mx = max(mx, s);
if (mx > i / 2) mx = i / 2, rt = x;
}else {
int s = query(dfn[rt] + siz[rt] - 1) - query(dfn[rt] - 1);
mx = max(mx, i - s);
if (mx > i / 2) mx = i / 2, rt = f[rt][0];
}
printf("%d ", i - mx * 2);
}
puts("");
for (int i = 1; i <= n; i++) add(dfn[i], -1);
}
}