AtCoder ARC #205 : D - Non-Ancestor Matching

ちょっと手間取った。
https://atcoder.jp/contests/arc205/tasks/arc205_d

問題

根付き木が与えられる。
互いに祖先・子孫関係にない2点をペアにすることを考える。
各点は1つのペアしか組めない場合、最大何ペア作れるか。

解法

部分木毎に、(ペアを組めていない頂点数,最大ペア数)の対を求めよう。
子頂点に対し上記値を求めた場合、各子頂点のペアを組めていない頂点同士でペアを組んでいく。
ただし、1つの子頂点だけペアを組めていない頂点が沢山ある場合、組み切れない場合があるので、その場合は他の子頂点において既にできているペアを分解して、まだペアを組めていない点とのペアを貪欲に組んでいこう。

int T,N;
vector<int> E[505050];

pair<int,int> dfs(int cur) {
	
	if(E[cur].size()==0) {
		return {1,0};
	}

	vector<pair<int,int>> V;
	FORR(e,E[cur]) {
		V.push_back(dfs(e));
	}
	sort(ALL(V));
	reverse(ALL(V));
	
	int cand=0;
	int pa=0;
	int i;
	for(i=1;i<V.size();i++) {
		cand+=V[i].first;
		pa+=V[i].second;
	}
	V[0].second+=pa;
	if(cand>=V[0].first) {
		V[0].second+=(cand+V[0].first)/2;
		V[0].first=(cand+V[0].first)%2;
	}
	else {
		V[0].first-=cand;
		V[0].second+=cand;
		int x=min(V[0].first/2,pa);
		V[0].second+=x;
		V[0].first-=x*2;
	}
	V[0].first++;
	return V[0];
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i].clear();
		for(i=1;i<N;i++) {
			cin>>x;
			E[x-1].push_back(i);
		}
		auto p=dfs(0);
		cout<<p.second<<endl;
	}
}

まとめ

方針はすぐ立ったんだけど、細かい実装ミスとかして手間取ってしまった。