Codeforces ECR #132 : E. XOR Tree

4問目で結構難しい回。
https://codeforces.com/contest/1709/problem/E

問題

木を成すグラフが与えられる。
各点には整数値が設定されており、パスの重さはパス上の頂点の整数値のxorとする。

いくつか点の設定値を書き換え、重さが0のパスが存在しないようにしたい。
最小何個の設定値を書き換える必要があるか。

解法

葉から見ていく。
今いる頂点から、SubTreeのどこかまでの頂点のパスの重さが0となってしまうなら、今いる頂点を2^(30+k)とすることで、その頂点を通るパスは必ず0にならないようにできる。
SubTree内の各点までのパスの重さを、マージテクの要領で管理していこう。

int N;
ll A[202020];
int V[202020];
set<int> S[202020];
int ret;
vector<int> E[202020];

void dfs(int cur, int pre) {
	V[cur]=A[cur];
	S[cur]={0};
	int ok=1;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		
		if(S[e].size()<S[cur].size()) {
			FORR(x,S[e]) {
				if(S[cur].count(x^V[e]^V[cur])) ok=0;
			}
			FORR(x,S[e]) {
				S[cur].insert(x^V[e]^A[cur]^V[cur]);
			}
		}
		else {
			FORR(x,S[cur]) {
				if(S[e].count(x^V[e]^V[cur])) ok=0;
			}
			FORR(x,S[cur]) {
				S[e].insert(x^V[e]^A[cur]^V[cur]);
			}
			swap(V[cur],V[e]);
			swap(S[cur],S[e]);
			V[cur]^=A[cur];
		}
		
	}
	
	if(ok==0) {
		ret++;
		S[cur].clear();
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	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<<ret<<endl;
}

まとめ

わかってしまえば簡単。