考虑固定一个重心，设 \(k\) 为重心最大子树大小，答案为 \(n - 2k\)。构造方法是往最大的子树塞叶子。
树的重心有一个很好的性质，就是加一个叶子，重心最多移动一条边的距离。简单证一下，设重心为 \(x\)，往儿子 \(u\) 的子树中加叶子。
- 如果 \(sz_u > \left\lfloor\frac{n}{2}\right\rfloor\)，那么 \(sz_u - 1 = \left\lfloor\frac{n}{2}\right\rfloor\)，并且 \(x\) 的其他子树大小 \(< \left\lfloor\frac{n}{2}\right\rfloor\)，那么 \(x\) 会下移到 \(u\)；
- 否则无事发生。
考虑树状数组维护每个点子树的大小，当前重心和当前的 \(k\)。只用考虑下移一条边的情况，因此是容易维护的。时间复杂度 \(O(n \log n)\)。
code
// Problem: D. Two Centroids
// Contest: Codeforces - Codeforces Round 873 (Div. 1)
// URL: https://codeforces.com/contest/1827/problem/D
// Memory Limit: 1024 MB
// Time Limit: 1500 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 500100;
const int logn = 22;
int n, head[maxn], len, st[maxn], times, ed[maxn], f[maxn][logn], dep[maxn];
struct edge {
int to, next;
} edges[maxn];
inline void add_edge(int u, int v) {
edges[++len].to = v;
edges[len].next = head[u];
head[u] = len;
}
namespace BIT {
int c[maxn];
inline void init() {
for (int i = 1; i <= n; ++i) {
c[i] = 0;
}
}
inline void update(int x, int d) {
for (int i = x; i <= n; i += (i & (-i))) {
c[i] += d;
}
}
inline int query(int x) {
int res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
inline int query(int l, int r) {
return query(r) - query(l - 1);
}
}
void dfs(int u) {
st[u] = ++times;
for (int i = 1; i <= 20; ++i) {
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
f[v][0] = u;
dep[v] = dep[u] + 1;
dfs(v);
}
ed[u] = times;
}
inline int jump(int x, int k) {
for (int i = 0; i <= 20; ++i) {
if (k & (1 << i)) {
x = f[x][i];
}
}
return x;
}
void solve() {
len = 0;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
head[i] = 0;
}
for (int i = 2, p; i <= n; ++i) {
scanf("%d", &p);
add_edge(p, i);
}
times = 0;
dfs(1);
BIT::init();
BIT::update(st[1], 1);
int x = 1, mx = 0;
for (int u = 2; u <= n; ++u) {
BIT::update(st[u], 1);
if (st[x] <= st[u] && st[u] <= ed[x]) {
int v = jump(u, dep[u] - dep[x] - 1);
int t = BIT::query(st[v], ed[v]);
if (t > u / 2) {
x = v;
mx = u / 2;
} else {
mx = max(mx, t);
}
} else {
int t = u - BIT::query(st[x], ed[x]);
if (t > u / 2) {
x = f[x][0];
mx = u / 2;
} else {
mx = max(mx, t);
}
}
printf("%d ", u - mx * 2);
}
putchar('\n');
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}