kmjp's blog

競技プログラミング参加記です

Codeforces #475 B. Destruction of a Tree

これに手間取りすぎて解けるC,Dも落とすというしょうもないことに。
http://codeforces.com/contest/963/problem/B

問題

木を成すグラフが与えられる。
辺が偶数本つながる頂点を、頂点と隣接辺ごと消す、という作業を繰り返し全頂点を消せるか。
消せるならその手順を示せ。

解法

1回で偶数本の辺が消えるので、元々の辺の数が偶数、すなわち頂点数が奇数でないと全頂点を消せない。
逆に連結成分内の頂点数が奇数であれば必ず全頂点を削除することができる。

根頂点からDFSで探索していくことを考える。
SubTree内の頂点数が奇数なら、親頂点が先に消え、SubTree内の頂点数が偶数ならSubTree側を先に消すことを考えよう。

あるSubTreeの頂点数が奇数の場合、その各子頂点のうちSubTreeの頂点数が奇数となるものは偶数個ある。
よってSubTreeの頂点数が偶数となるものを先に探索する。上記条件より再帰的にそのようなSubTreeは先に消え去る。
あとは今見ている頂点に残されているのは奇数個の頂点を持つSubTreeが偶数個なので、今見ている頂点を消した後、残されたSubTreeを消しに行けばよい。

SubTreeの頂点数が偶数の場合、上記条件より親向きの辺が残った状態で探索を行う。
こちらは子頂点のSubTree内の頂点数が奇数となるのは奇数個なので、同様の手順を取れば親方向の辺と合わせて頂点を消すことができる。

結局各頂点において

  • SubTree内の頂点数が偶数個の子頂点を探索する
  • 見ている頂点を消す
  • SubTree内の頂点数が奇数個の子頂点を探索する

の順を取ればよい。

int N;
set<int> E[202020];
set<int> cand;
int C[202020];
vector<int> V;

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

void dfs2(int cur,int pre) {
	FORR(e,E[cur]) if(e!=pre) {
		if(C[e]%2==0) dfs2(e,cur);
	}
	V.push_back(cur);
	FORR(e,E[cur]) if(e!=pre) {
		if(C[e]%2==1) dfs2(e,cur);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N%2==0) return _P("NO\n");
	
	for(i=1;i<=N;i++) {
		cin>>x;
		if(x) {
			E[i].insert(x);
			E[x].insert(i);
		}
	}
	dfs(1,1);
	dfs2(1,1);
	
	cout<<"YES"<<endl;
	FORR(v,V) cout<<v<<endl;
	
}

まとめ

えらく手間取ってしまった。