Codeforces #589 Div2 F. One Node is Gone

まぁまぁ手間取った。
https://codeforces.com/contest/1228/problem/F

問題

(2^N-1)頂点の完全二分木があったとする。
ここから、根以外の頂点を1つ取り除き、取り除く前の親頂点と子頂点を直接つなげる操作を行ったとする。

(2^N-2)頂点の木が与えられる。
この木が上記手順で作れるかどうか判定し、作れるなら消えた頂点の親頂点はどこにあったかその候補を答えよ。

解法

いろんな解法がありそう。
完全二分木であれば子方向の各隣接点の先にある頂点数は等しいはずなので、そこに1ずれがある場合そちらがわに欠けた点がある、として候補を絞った。
深さをベースに考えてもよさそう。

int D,N;
vector<int> E[1<<17];
int C[1<<17],P[1<<17];
set<int> R;

int dfs(int cur,int pre) {
	P[cur]=pre;
	C[cur]=1;
	FORR(e,E[cur]) if(e!=pre) C[cur]+=dfs(e,cur);
	return C[cur];
}

int ok(int cur,int pre) {
	vector<int> C;
	FORR(e,E[cur]) if(e!=pre) {
		C.push_back(ok(e,cur));
	}
	sort(ALL(C));
	if(C.empty()) return 0;
	if(C[0]==-1) return -1;
	if(C.size()==1) {
		if(C[0]==0) {
			R.insert(cur+1);
			return C[0]+1;
		}
	}
	if(C.size()==2) {
		if(C[0]==C[1]) {
			return C[0]+1;
		}
	}
	if(C.size()==3) {
		if(C[0]==C[1]&&C[0]+1==C[2]) {
			R.insert(cur+1);
			return C[2]+1;
		}
	}
	return -1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D;
	N=(1<<D)-2;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,-1);
	vector<int> CV;
	int cur;
	FOR(cur,N) {
		if(E[cur].size()==1) {
			vector<int> cand;
			FORR(e,E[cur]) {
				if(e==P[cur]) {
					cand.push_back(N-C[cur]);
				}
				else {
					cand.push_back(C[e]);
				}
			}
			sort(ALL(cand));
			if(cand[0]==1) CV.push_back(cur);
		}
		if(E[cur].size()==2) {
			vector<int> cand;
			FORR(e,E[cur]) {
				if(e==P[cur]) {
					cand.push_back(N-C[cur]);
				}
				else {
					cand.push_back(C[e]);
				}
			}
			sort(ALL(cand));
			if(cand[0]+1==cand[1]) CV.push_back(cur);
		}
		if(E[cur].size()==3) {
			vector<int> cand;
			FORR(e,E[cur]) {
				if(e==P[cur]) cand.push_back(N-C[cur]);
				else cand.push_back(C[e]);
			}
			sort(ALL(cand));
			if(cand[0]==cand[1] && cand[0]+cand[1]+1==cand[2]) CV.push_back(cur);
		}
	}
	set<int> TR;
	FORR(c,CV) {
		if(ok(c,-1)>=0) {
			FORR(r,R) TR.insert(r);
		}
	}
	
	cout<<TR.size()<<endl;
	FORR(r,TR) cout<<r<<" ";
	
}

まとめ

Div2とはいえFの割には簡単？