Codeforces #429 Div1 B. Leha and another game about graph

遠回りしてしまった。
http://codeforces.com/contest/840/problem/B

問題

連結無向グラフが与えられる。
また各頂点vに対し値D[v]が設定される。

このグラフの部分グラフを作り、各頂点の次数の偶奇がD[v]と一致するようにせよ。
なお、D[v]は"偶奇を問わない"を意味する値が入る場合もある。

解法

閉路をなくし木となることを考える。
次数が奇数でなければならない頂点が２つu,vとあったとする。
木においてu-vのパス上の辺の有無を切り替えれば、u,vだけ次数が1変化し、その他は変化しない。

よってそのような頂点を2つずつ対にし、あとは累積和の要領で各辺の有無を判定する。
次数が奇数でなければならない頂点が奇数個ある場合、"偶奇を問わない"頂点とペアにしよう。

int N,M;
int DD[303030];
vector<pair<int,int>> E[303030];
int PE[303030];
int P[300005],D[300005];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;
vector<int> C[2];
vector<int> DC[303030];
int X[303030];

void dfs(int cur) {
	DC[D[cur]].push_back(cur);
	ITR(it,E[cur]) {
		if(it->first!=P[cur]) D[it->first]=D[cur]+1, P[it->first]=cur, dfs(it->first);
		if(it->first==P[cur]) PE[cur]=it->second;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		if(x==1) C[0].push_back(i);
		if(x==-1) C[1].push_back(i);
	}
	
	if(C[0].size()%2==1 && C[1].size()) C[0].push_back(C[1][0]);
	if(C[0].size()%2==1) return _P("-1\n");
	
	FOR(i,M) {
		cin>>x>>y;
		if(uf[x]!=uf[y]) {
			E[x-1].push_back({y-1,i+1});
			E[y-1].push_back({x-1,i+1});
			uf(x,y);
		}
	}
	dfs(0);
	
	FOR(i,C[0].size()) X[C[0][i]]^=1;
	
	vector<int> R;
	for(i=N;i>0;i--) FORR(v,DC[i]) {
		X[P[v]]^=X[v];
		if(X[v]) R.push_back(PE[v]);
	}
	sort(ALL(R));
	cout<<R.size()<<endl;
	FORR(r,R) cout<<r<<endl;
	
	
}

まとめ

無駄にLCAのコードとか書いてしまった。