Hello 2023 : F. Xorcerer's Stones

本番こっちの方がすんなり解けているな。
https://codeforces.com/contest/1779/problem/F

問題

根付き木が与えられる。
各点には0～31の値のいずれかが書かれている。
点を1つ指定すると、以下が行われる。

• SubTree内の全点の値のxorを取った値をxとする。
• SubTree内の全点のxorがxとなる。

全点の値を0にできるか、できるならその手順を求めよ。

解法

各点について、SubTree内のxorの値を0～31にできるかどうか、できる場合各子頂点の値をどうすればよいかを、葉から順にDPで求めて行こう。
その際、SubTreeの頂点数が偶数の場合は、その点を2回指定すればSubTree内をすべて0にできる。

最終的に根頂点のSubTreeのxorを0にできることが確定したら、DPの復元を行おう。

int N,A[202020];
int P[202020];
vector<int> E[202020];
int C[202020];

vector<int> dp[202020][32];
vector<int> ret;

void dfs(int cur,int v) {
	if(dp[cur][v].back()==33) {
		ret.push_back(cur);
		ret.push_back(cur);
		return;
	}
	int k=E[cur].size();
	while(k) {
		int y=dp[cur][v][k];
		dfs(E[cur][k-1],y);
		k--;
		v^=y;
	}
}

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>>P[i+1];
		P[i+1]--;
		E[P[i+1]].push_back(i+1);
	}
	
	for(i=N-1;i>=0;i--) {
		FOR(j,32) dp[i][j].resize(E[i].size()+1,-1);
		dp[i][A[i]][0]=0;
		C[i]=1;
		FOR(j,E[i].size()) {
			k=E[i][j];
			C[i]+=C[k];
			FOR(x,32) if(dp[i][x][j]!=-1) {
				FOR(y,32) if(dp[k][y].back()!=-1) {
					dp[i][x^y][j+1]=y;
				}
			}
		}
		if(C[i]%2==0) {
			dp[i][0].back()=33;
		}
	}
	
	if(dp[0][0].back()==-1) {
		cout<<-1<<endl;
	}
	else {
		dfs(0,0);
		if(N%2) ret.push_back(0);
		cout<<ret.size()<<endl;
		FORR(r,ret) cout<<r+1<<" ";
		cout<<endl;
	}
	
	
}

まとめ

Eよりすんなり解いてた。