Codeforces #987 : Div2 E. Penchick and Chloe's Trees

E問題の割にAC数多いな。
https://codeforces.com/contest/2031/problem/E

問題

根付き木が与えられる。
深さdの完全二分木から、以下の手順を繰り返して入力の木にしたい。

• 点vに対し、子の頂点集合Sと、親頂点pがあったとする。
• 点vとvにつながる辺を消し、Sの各頂点とpの間に辺を加える。

最低限必要なdの最小値を求めよ。

解法

葉側から順に、各頂点のSubTreeを構成するときに必要な深さdを再帰的に求めよう。
各点vに対し、子頂点が3つ以上ある場合、うち必要な深さdが小さい2個を選び、vから取り除いて、vの子頂点cを追加してcの下にぶら下げる。
このようにして、vの子頂点が2個以下になるようにする。

int T,N;
int P[1010101];
vector<int> C[1010101];
multiset<int> V[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			C[i].clear();
			V[i].clear();
		}
		FOR(i,N-1) {
			cin>>P[i+1];
			P[i+1]--;
			C[P[i+1]].push_back(i+1);
		}
		
		for(i=N-1;i>=0;i--) {
			if(V[i].empty()) {
				V[P[i]].insert(0);
			}
			else {
				while(V[i].size()==1) V[i].insert(0);
				while(V[i].size()>2) {
					x=*V[i].begin();
					V[i].erase(V[i].begin());
					y=*V[i].begin();
					V[i].erase(V[i].begin());
					V[i].insert(y+1);
				}
				if(i) V[P[i]].insert(*V[i].rbegin()+1);
			}
		}
		cout<<*V[0].rbegin()+1<<endl;
		
	}
}

まとめ

自分が作ると、逆に入力の木からどんな深さの完全二分木が作れるか、という問題になりそう。