Submission #69085083

---

Source Code Expand

/*
Author : Mikira
9/6/2025 9:20:09 PM
*/

#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<LL, LL> PLL;
typedef pair<LL, LL> pll;
typedef long double ld;

#define rep(i, a, b) for(int i = a; i < int(b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second

const double EPS = 1e-9;
const int INFMEM = 63;

// Do dir^1 to get reverse direction
const int dx[8] = {0,0,1,-1,1,-1,1,-1};
const int dy[8] = {1,-1,0,0,1,-1,-1,1};
const char dch[4] = {'R','L','D','U'};

// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;

inline void fasterios(){
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
}
#define endl '\n'
const int MOD = 1000000007;
// const int MOD = 998244353;

const int kN = 5e5;
vector <int> edge[kN + 5];
int memo[kN + 5];
int subtreeSize[kN + 5];
void dp(int pos) {
  subtreeSize[pos] = 1;
  vector <int> child;
  int maxMemoChild = -1;
  trav(nx, edge[pos]) {
    dp(nx);
    child.pb(nx);
    subtreeSize[pos] += subtreeSize[nx];
    if(maxMemoChild == -1) maxMemoChild = nx;
    if(memo[maxMemoChild] < memo[nx]) maxMemoChild = nx;
  }
  memo[pos] = 1;
  if(maxMemoChild != -1) {
    int maxDp = 0;
    trav(nx, edge[pos]) {
      if(nx == maxMemoChild) continue;
      int currentTaken = min(subtreeSize[nx], memo[maxMemoChild]);
      maxDp += currentTaken;    
    }
    memo[pos] += max(0, memo[maxMemoChild] - maxDp);
  }
} 
int solve(){
  int n; cin >> n;
  for(int i = 1;i <= n;++i) {
    edge[i].clear();
  }
  for(int i = 2;i <= n;i++) {
    int p; cin >> p;
    edge[p].pb(i);
  }
  dp(1);
  cout << (n - memo[1]) / 2 << endl;
  return 0;
}

int main(){
  fasterios();
  int testCases = 1, tc = 0;
  cin >> testCases;
  while(++tc <= testCases){
    // cout << "Case #" << tc << ": ";
    solve();
  }
}

Submission Info

Judge Result