SRM719 Div2 Hard

問題

TopCoder Statistics - Problem Statement

考察

根ノードから任意のノードまでのパスのXORの計算を行う。

xor[V] = 根ノードから任意のノードVまでのXOR

そうすると任意のノードVから他の任意のノードUまでのパスのXORの計算結果は
xor[V] ^ xor[U]になる。これはXORの性質を考えると分かる。
A xor B = X
A xor C = Y
X xor Y = B xor C

詳しくはkmjpさんの解説記事で
kmjp.hatenablog.jp

ソースコード

下のコードでやっていることは

ノード0から任意のノードvまでのXORを求めとく。
制約からノード数<=1000なので、パスの始点ノードsと終点ノードtを全探索してxor[s]^xor[t]をSetに挿入。
0<=w[i]<=1023なのでXORの計算結果は高々1024通りしかない。
あとはSetから重複を許して値を二つ選んでXORの最大値を求める。

import java.util.HashSet;
import java.util.Set;
public class TwoDogsOnATree{

        public int maximalXorSum(int[] parent,int[] w){

            int N = parent.length + 1;
            int[] xor = new int[N];

            for(int i = 1;i < N;i++){
                int v = i;

                while(v > 0){
                    xor[i] ^= w[v-1];
                    v = parent[v-1];
                }
            }
            Set<Integer> xorSet = new HashSet<>();
            for(int i = 0;i < N;i++){
                for(int j = 0;j < N;j++){
                    xorSet.add(xor[i]^xor[j]);
                }
            }

            int ans = 0;
            for(int a : xorSet){
                for(int b : xorSet){
                    ans = Math.max(ans,a^b);
                }
            }
            return ans;
        }
    }