算法

其实和上一题是一个题目。我们需要利用异或的两个性质。
a ^ a = 0
a ^ 0 = a
也就是说，0和任何树异或都相当于数本身，任意两个相同的数异或为0。
所以我们可以用O(n)的时间来对整棵树遍历，选定一个根节点，算出所有点到根节点的距离。
然后再从这n个点中求两两异或的最大值。

时间复杂度

O(nlogn)

代码

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

class Node {
    Node[] sons;
    public Node() {
        sons = new Node[2];
    }
}

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] edges = new int[n - 1][3];
        for (int i = 0; i < n - 1; ++i) {
            edges[i][0] = in.nextInt();
            edges[i][1] = in.nextInt();
            edges[i][2] = in.nextInt();
        }
        in.close();
        List<int[]>[] graph = buildGraph(edges, n);
        int[] arr = new int[n];
        dfs(arr, graph, 0, -1, 0);
        System.out.println(maxXor(arr));
    }

    private static int maxXor(int[] arr) {
        Node trie = new Node();
        for (int a : arr) {
            insert(a, trie);
        }
        int curMax = 0;
        for (int a : arr) {
            int temp = query(a, trie, curMax);
            curMax = Math.max(temp, curMax);
        }
        return curMax;
    }

    private static void insert(int a, Node trie) {
        for (int i = 30; i >= 0; --i) {
            int cur = (a >> i) & 1;
            if (trie.sons[cur] == null) {
                trie.sons[cur] = new Node();
            }
            trie = trie.sons[cur];
        }
    }

    private static int query(int a, Node trie, int curMax) {
        int ans = 0;
        for (int i = 30; i >= 0; --i) {
            int cur = (a >> i) & 1;
            if (trie.sons[1 ^ cur] != null) {
                ans ^= (1 << i);
                trie = trie.sons[cur ^ 1];
            } else {
                trie = trie.sons[cur];
            }
            if (curMax > (1 << i) && ans == 0) return curMax;
        }
        return ans;
    }

    private static List<int[]>[] buildGraph(int[][] edges, int n) {
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; ++i) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            graph[e[0]].add(new int[]{e[1], e[2]});
            graph[e[1]].add(new int[]{e[0], e[2]});
        }
        return graph;
    }

    private static void dfs(int[] arr, List<int[]>[] graph, int cur, int par, int xor) {
        arr[cur] = xor;
        for (int[] next : graph[cur]) {
            if (next[0] != par) {
                dfs(arr, graph, next[0], cur, xor ^ next[1]);
            }
        }
    }
}