提出 #69086498

---

ソースコード 拡げる

//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#include"atcoder/all"
using namespace atcoder;
typedef modint998244353 mi;
using namespace std;
#define all(a) a.begin(),a.end()
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
#define compress(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
constexpr ll mod=998244353;
constexpr ll inf=3e18;

void solve(){
	int n;
	cin>>n;
	vector<int>p(n);
	vector<vector<int>>G(n);
	for(int i=1;i<n;i++){
		cin>>p[i];
		p[i]--;
		G[p[i]].push_back(i);
	}
	vector<int>d(n),weight(n);
	function<void(int)> dfs=[&](int now){
		weight[now]+=1;
		for(auto &e:G[now]){
			d[e]=d[now]+1;
			dfs(e);
			weight[now]+=weight[e];
		}
	};
	
	dfs(0);
	int now=0,stock=0,ans=0;
	while(G[now].size()){
		int val=-1,v=-1;
		for(auto &e:G[now]){
			stock+=weight[e];
			if(val<weight[e]){
				val=weight[e];
				v=e;
			}
		}
		stock-=val;
		now=v;
		if(stock){
			stock--;
			ans++;
		}
	}
	ans+=stock/2;
	cout<<ans<<endl;

}

int main(){
	int t;
	cin>>t;
	while(t--)solve();
}

提出情報

ジャッジ結果