Codeforces #851 : Div2 F. XOR, Tree, and Queries

本番中に詰め切れず…。
https://codeforces.com/contest/1788/problem/F

問題

木を成すグラフが与えられる。
ここで各辺に整数値を設定したい。

追加でクエリが与えられており、2点間の辺の整数値のxorの値が指定される。
条件を満たす辺の設定値のうち、xorを取った値が最小となるものを答えよ。

解法

各点vに対し、根頂点からvまでの辺の設定値のxorをP(v)とする。
クエリがu,v間の辺のxor値がxであるとき、これはP(u) xor P(v) = xであることを意味する。

元のグラフとは別の、グラフを考える。
クエリから点(u,v)間にxの重さの辺を張る。
このグラフで各連結成分内でDFSを行い、クエリに反しないようにP(v)を定めて行く。

あとは辺のxor値を小さくしたいが、辺の設定値のxorの値は、次数が奇数の頂点vにおけるP(v)のxorに一致する。
よって次数が偶数の点vのP(v)の値はどうでも良い。
そこでそのような次数が奇数かつ後者のグラフで連結成分内の頂点数が奇数となる点を1個選び、xorが0となるようにP(v)を調整しよう。

int N,Q;
int U[252525],V[252525];
int C[252525];
vector<pair<int,int>> E[252525];
int R[252525];
int S[252525];
int NE[252525];

void dfs(int cur,int v,int root) {
	if(R[cur]!=-1) {
		if(R[cur]!=v) {
			cout<<"No"<<endl;
			exit(0);
		}
		return;
	}
	R[cur]=v;
	C[cur]=root;
	S[root]^=NE[cur];
	FORR2(e,w,E[cur]) dfs(e,v^w,root);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>U[i]>>V[i];
		NE[U[i]-1]^=1;
		NE[V[i]-1]^=1;
	}
	
	FOR(i,Q) {
		cin>>x>>y>>k;
		E[x-1].push_back({y-1,k});
		E[y-1].push_back({x-1,k});
	}
	MINUS(R);
	FOR(i,N) if(R[i]==-1) dfs(i,0,i);
	
	int ret=0;
	FOR(i,N) if(NE[i]) ret^=R[i];
	FOR(i,N) if(C[i]==i&&S[i]) {
		FOR(j,N) if(C[j]==i) R[j]^=ret;
		break;
	}
	
	
	cout<<"Yes"<<endl;
	FOR(i,N-1) cout<<(R[U[i]-1]^R[V[i]-1])<<" ";
}

まとめ

コード量は多くないけど、ちょっと考察が要る。