yukicoder : No.1928 Make a Binary Tree

実装軽め。
https://yukicoder.me/problems/no/1928

問題

根付き木が与えられる。
この根付き木に対し、以下の処理を何回でも行えるとする。

• 頂点vとその親頂点uの間の辺を削除し、uの祖先の頂点wとvの間に辺を追加する。
• 頂点vとその親頂点uの間の辺を削除し、v側の成分を取り除く。

この木を二分木にするとき、最大の頂点数を求めよ。

解法

各点子頂点を2個まで持つことができる。
そこで、Subtreeのうち大きな上位2つまでを子頂点としよう。
もし元々3個以上子がある場合、3番目以降のSubTreeは、親に送っていこう。
もし祖先に子頂点が1個しかないところがあれば、親に送った子頂点をぶら下げることができる。

また、3位以降のSubTreeのサイズを管理するため、いわゆるマージテクを用いるとよい。

int N;
vector<int> E[202020];
multiset<int> M[202020];

void dfs(int cur,int pre) {
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		
		if(M[cur].size()<M[e].size()) swap(M[cur],M[e]);
		FORR(v,M[e]) M[cur].insert(v);
	}
	
	if(M[cur].empty()) {
		M[cur].insert({1});
	}
	else if(M[cur].size()==1) {
		int x=*M[cur].begin();
		M[cur]={x+1};
	}
	else {
		int x=*M[cur].rbegin();
		M[cur].erase(M[cur].find(x));
		int y=*M[cur].rbegin();
		M[cur].erase(M[cur].find(y));
		M[cur].insert(x+y+1);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,0);
	cout<<*M[0].rbegin()<<endl;
}

まとめ

マージテクを知っていると、あまり迷うことがない。