Codeforces #417 Div2 E. Sagheer and Apple Tree

こっちの方が問題はシンプルか。
http://codeforces.com/contest/812/problem/E

問題

根付き木が与えられる。
各根から葉までの距離の偶奇はすべての葉で一致する。
初期状態で各頂点に正の数のリンゴがあるものとする。

この木を使い2人でターン制のゲームを行う。
各自のターンでは、1つ以上リンゴがある頂点を1つ選び、一部のリンゴを子頂点に移動させる。
ただし葉の場合子頂点がないのでリンゴを木から取り除く。
自分の手番でリンゴを移動できない場合負けとなる。

ここで、後手のプレイヤーは最初に任意の2頂点のリンゴを入れ替え可能とする。
後手必勝となるような入れ替え方の組み合わせを答えよ。

解法

仮に根から葉頂点までの距離を偶数とする。
するとこの問題は距離が偶数の頂点のリンゴ数に対しNimを行うのと同等とみなせる。

今回は後手必勝にしたいので、リンゴの入れ替えにより偶数の頂点のリンゴ数のxorを取った値が0になった場合、先手が何をしても後手が元の状態に戻せることを示す。
先手が偶数→奇数の位置にリンゴを動かした場合、xorの値が非0になるので、同様に偶数→奇数の位置にリンゴを動かしxorの値を0にできる。
奇数→偶数の位置にリンゴを動かした場合、その動かしたリンゴをまたそのままその子頂点の奇数位置(もしくは木の外)に動かせば、やはりxorの値を0にできる。

よってまずは葉頂点と距離のパリティが同じ頂点群に対し、リンゴの数のxorを求めよう。
元々xorを取った値が0の場合、リンゴが同数の頂点を2つ選べばxor値も変わらない。
そうでない場合、距離のパリティが偶数の点と奇数の点を1つずつ選び、xorの値が0になるようにしよう。
これは先にパリティの偶奇それぞれであるリンゴの数を満たす頂点がいくつあるかをカウントしておけばよい。

int N;
int A[101010];
int P[101010];
vector<int> E[101010];
int D[101010];
int nim,mad;

void dfs(int cur,int d) {
	mad=max(mad,d);
	D[cur]=d;
	FORR(e,E[cur]) dfs(e,d+1);
}

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;
		E[x-1].push_back(i+1);
	}
	
	dfs(0,0);
	map<int,int> M;
	int nim=0;
	FOR(i,N) {
		if(D[i]%2==mad%2) {
			nim^=A[i];
		}
		else {
			M[A[i]]++;
		}
	}
	ll ret=0;
	FOR(i,N) if(D[i]%2==mad%2) ret += M[nim^A[i]];
	if(nim==0) {
		ll num[2]={};
		FOR(i,N) {
			if(D[i]%2==mad%2) ret+=num[0],num[0]++;
			else ret+=num[1],num[1]++;
		}
	}
	cout<<ret<<endl;
}

まとめ

変則Nimでした。
最初に位置を入れ替えるというのがちょっと目新しいね。