Codeforces #783 : Div1 D. Edge Elimination

問題設定は割とシンプル。
https://codeforces.com/contest/1667/problem/D

問題

木を成す無向グラフが与えられる。
辺同士が隣接するとは、端点を1つ共有している場合を指す。

この木から、偶数本の辺に隣接する任意の辺を削除する、という手順を繰り返し、全辺を削除できるか判定せよ。
また、削除できるならその手順を示せ。

解法

辺のパリティを両端で隣接する辺の数の偶奇と定義する。

各点に対し、辺の削除順は辺のパリティが偶奇交互に並ばなければならない。
よって、各点における両パリティの辺の数の差は1以下でなければならない。
DFSで葉から順に判定し、辺のパリティを定めながら、この条件をチェックしよう。

int T,N;
vector<int> E[202020];
int U[202020],V[202020];
int parity[202020];

int dfs(int cur,int pre) {
	int C[2]={};
	FORR(e,E[cur]) if(e!=pre) {
		int r=dfs(e,cur);
		if(r<0) return -1;
		C[r]++;
	}
	
	parity[cur]=0;
	if(cur!=pre) {
		parity[cur]=C[0]>=C[1];
		C[parity[cur]]++;
	}
	
	if(C[0]>C[1]||C[1]>C[0]+1) return -1;
	return parity[cur];
	
	
}

void dfs2(int cur,int pre) {
	vector<int> V[2];
	FORR(e,E[cur]) {
		if(e==pre) {
			V[parity[cur]].push_back(cur);
		}
		else {
			V[parity[e]].push_back(e);
		}
	}
	int i;
	int cid=E[cur].size()%2;
	FOR(i,E[cur].size()) {
		int x=V[cid].back();
		V[cid].pop_back();
		cid^=1;
		
		if(x==cur) {
			cout<<x<<" "<<pre<<endl;
		}
		else {
			dfs2(x,cur);
		}
		
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i+1].clear();
		for(i=1;i<=N-1;i++) {
			cin>>U[i]>>V[i];
			E[U[i]].push_back(V[i]);
			E[V[i]].push_back(U[i]);
		}
		
		x=dfs(1,1);
		if(x==-1) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
			dfs2(1,1);
		}
			
			
	}
}

まとめ

こういう条件をぱっと思いつける気がしないなぁ。