TopCoder SRM 719 Div2 Hard TwoDogsOnATree

気づいてしまえば単純。
https://community.topcoder.com/stat?c=problem_statement&pm=14673

問題

N頂点の木を成す無向グラフが与えられる。
各辺eには値W[e]が設定されている。

このグラフから、まずパスを1つ選択する。
そのパス上のW[e]のxorを取った値をAとする。

次に、そのパス上の辺をすべて取り除き、再度同様に残された辺からパスを1つ選択してパス上のW[e]のxorを取った値をBとする。
こうして得られる2値A,Bに対し、A xor Bの最大値を求めよ。

解法

頂点0からvまでのパスにおける辺eのW[e]のxorをX[v]とする。
パス(x,y)があるとき、このパスにおける辺eのW[e]のxorはX[x]^X[y]とO(1)で解ける。

1つめのパスの端点を(a,b)、2つめのパスの端点を(c,d)とする。
パス(a,b)と(c,d)が共通辺をもたないなら、A=X[a]^X[b]、B=X[c]^X[d]で結局A^B=X[a]^X[b]^X[c]^X[d]となる。

実はこれは共通辺をもつ場合も同様に成り立つ。
パス(a,b)と(c,d)が共通辺を持つ場合、端点を組み替えて(a,c)と(b,d)または(a,d)と(b,c)のパスにすれば、共通辺をもたないようにできる。
このケースも結局A^B=X[a]^X[b]^X[c]^X[d]となる。

こうなると問題は簡単で、頂点を重複を許して4つ(a,b,c,d)選び、X[a]^X[b]^X[c]^X[d]の最大値を求める問題に帰着できる。
以下のコードは頂点を4つ選ぶDPをしているが、他の参加者の回答ではAの候補とBの候補をそれぞれ列挙し、A^Bの最大値を求めているようだ。

class TwoDogsOnATree {
	public:
	
	int maximalXorSum(vector <int> parent, vector <int> w) {
		int N=parent.size()+1;
		int V[1010]={};
		int i,j,x,y;
		int dp[5][1024]={};
		dp[0][0]=dp[1][0]=dp[2][0]=dp[3][0]=dp[4][0]=1;
		for(i=1;i<N;i++) {
			V[i]=V[parent[i-1]]^w[i-1];
			FOR(x,4) FOR(j,1024) if(dp[x][j]) dp[x+1][j^V[i]] |= 1;
		}
		
		for(i=1023;i>=0;i--) if(dp[4][i]) return i;
		return -1;
	}
}

まとめ

考察が終われば実装は簡単。