我的思路是按层贪心。对于只有一个点的一层，如果它前面有奇数个数个点的层，它就有 1 贡献；反之如果前面有偶数个数个点的层，就多一个奇数个数的层，没有贡献。奇数和偶数层的贡献就是 个数/2 下取整。

感觉很对，求 hack。

#include<bits/stdc++.h>
// #pragma GCC optimize ("O2")
#define int long long
#define ldb long double 
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
using namespace std;
const int N=5e5+10;
int fa[N],cnt[N];
int n,m;
vector<int> p[N];
void dfs(int x,int y){
    cnt[y]++;
    for(auto u:p[x]){
        dfs(u,y+1);
    }
}
void solve(){
    int i;
    dfs(1,1);
    int ans=0;
    stack<int> s[2];
    For(i,1,n){
        if(cnt[i]==1){
            if(s[1].size()){
                auto num1=s[1].top();
                s[1].pop();
                num1--;
                if(num1) s[0].push(num1);
                ans++;
            }
            else if(s[0].size()){
                auto num0=s[0].top();
                s[0].pop();
                num0--;
                if(num0>1) s[1].push(num0);
            }
        }
        else if(cnt[i]%2) s[1].push(cnt[i]-2);
        else if(cnt[i]%2==0&&cnt[i]>2) s[0].push(cnt[i]-2);
        ans+=cnt[i]/2;
    }
    int len=s[1].size();
    // cout<<len<<'\n';
    cout<<ans+len/2<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t,i;
    cin>>t;
    while(t--){
        cin>>n;
        For(i,2,n) cin>>fa[i],p[fa[i]].pb(i);
        solve();
        For(i,1,n) p[i].clear();
        For(i,1,n) cnt[i]=0;
    }
    return 0;
}