综上，我们以 $O(n\log n)$ 的优秀复杂度解决了此题。
:::success[Code]
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 5e5 + 7;
int n, f[N][20], g[N][20], dep[N], du[N], x, y, r, t[N];
inline int LCA(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
for (int i = 19; i >= 0; i--)
if (dep[f[u][i]] >= dep[v])
u = f[u][i];
if (u == v)
return u;
for (int i = 19; i >= 0; i--)
if (f[u][i] != f[v][i])
u = f[u][i], v = f[v][i];
return f[u][0];
}
inline void add(int u, int c)
{
for (int i = 0; u && i < 20; i++, u = t[u])
g[u][i] += c;
}
inline void update(int u, int c)
{ // 根从u换成c
for (int i = 1; i < 20; i++)
g[u][i] -= g[c][i - 1];
for (int i = 1; i < 20; i++)
g[c][i] += g[u][i - 1];
t[c] = 0, t[u] = c;
}
inline int calc(int u, int k)
{
for (int i = 19; i >= 0; i--)
if ((k >> i) & 1ll)
u = f[u][i];
return u;
}
inline bool check(int k)
{
if (x == y && g[x][k] > 0)
return 1;
if (x != y && (g[x][k] > 0 || g[y][k] > 0))
return 1;
return 0;
}
inline void insert(int u)
{
int l = LCA(u, y), d = dep[u] + dep[y] - 2 * dep[l];
if (x == y)
{
if (d <= r)
return;
r++;
if (l == y)
{
int ny = calc(u, d - 1);
update(y, ny), x = y, y = ny;
}
else
x = f[y][0];
return;
}
if (l == y && d >= r)
x = y;
if (l != y && d > r)
update(y, x), y = x;
}
inline void solve()
{
cin >> n;
for (int i = 0; i <= n; i++)
dep[i] = 0, du[i] = 0, t[i] = 0;
for (int i = 0; i <= n; i++)
for (int j = 0; j < 20; j++)
f[i][j] = g[i][j] = 0;
cout << "1 ";
dep[1] = 1, x = y = 1, r = 0, g[1][0] = 1;
for (int i = 2; i <= n; i++)
{
int p;
cin >> p;
du[p]++, du[i]++, t[i] = p;
if (du[p] > 3)
{
for (int j = i; j <= n; j++)
{
if(j!=i)cin >> p;
cout << -1 << " \n"[j == n];
}
return;
}
else if (du[p] == 3)
add(p, -1);
add(i, 1);
dep[i] = dep[p] + 1;
f[i][0] = p;
for (int j = 1; j < 20; j++)
f[i][j] = f[f[i][j - 1]][j - 1];
insert(i);
int res = 0;
for (int i = 0; i < 20; i++)
if (check(i))
{
res = i;
break;
}
cout << 1 + r + res << " \n"[i == n];
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
}
```
:::