1914F - Programming Competition - CodeForces Solution

/*

    M     M          A      TTTTTTT   H    H
   M M   M M        A A        T      H    H
  M   M M   M      A___A       T      H----H
 M     M     M    A     A      T      H    H
M      M      M  A       A     T      H    H

   ___    ____    ___    ___
  /   \  |    |  /   \      |
      /  |    |      /      |
   __/   |    |   __/    ===|
  |      |    |  |          |
  |___   |____|  |___    ___|


k     k   eee   r       b     eee   r                sss
k   k     e     rr      b     e     rr       oo     s   s
kkk       e     rr rrr  b     e     rr rrr  o  o     s   s
kk        eee   rr      bbbb  eee   rr      o  o      s
k   k     e     rr      b  b  e     rr      o  o    s  s
k     k   eee   rr      bbbb  eee   rr       oo      sss

*/
/*
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#pragma GCC target("avx2,fma")
*/
#include <bits/stdc++.h>

#define ll long long
#define ld double
#define el "\n"
#define N "NO"
#define Y "YES"
#define fx(i) fixed << setprecision(i)
/*\
4
2
2 2 1 1
2
1 2 2 1
2
1 2 1 2
5
3 4 4 5 3 1 1 5 2 2

*/
const ld pi = acos(-1);
const ld eps = 1e-6;
const ll mod = 998244353;
const ll oo = 1e15 + 7;
const int lim = 1000001;
using namespace std;
ll n,ans;
vector<int>st,mx;
vector<vector<int>>ad;

void dfs(ll nd){
 int sn=0;
   for(auto u:ad[nd])
    {dfs(u);
     st[nd]+=st[u]+1;
    if(mx[nd]<mx[u]+1)
    mx[nd]=mx[u]+1,sn=u;}
    mx[nd]=max(0,mx[nd]-st[nd]+st[sn]+1);
    if(!mx[nd]&&(st[nd]&1))mx[nd]=1;
}
void solving_problem()
{
    cin>>n;
    ad.clear();
    mx.clear();
    st.clear();
    mx.resize(n+1,0);
    st.resize(n+1,0);
    ad.resize(n+1);
    ans=0;
    for(int i=2,p;i<=n;i++){
        cin>>p;
        ad[p].push_back(i);
    }
        dfs(1);
    cout<<(n-mx[1])/2<<el;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int test = 1;
    //sv();
    cin >> test;
    while (test--)
        solving_problem();
    return 0;
}