题解 | 牛牛的糖果树

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static class Node {
        public int id = 0;
        public int color = 0;
        public ArrayList<Node> children = new ArrayList<>();

        public Node(int id) {
            this.id = id;
        }

        public Node() {

        }

        public String toString() {
            return String.valueOf(id);
        }
    }

    public static int gMax = -1;

    public static Map<Integer, Integer> DFS( Node head,
            Set<Integer> visited) {

        Map<Integer, Integer> colorTimes = new HashMap<>();
        int ret = 0;
        int old =  0;
        colorTimes.put(head.color, old + 1);

        visited.add(head.id);

        for (Node item : head.children) {
            if (visited.contains(item.id)) continue;

            Map<Integer, Integer> childColors = DFS(item, visited);
            for (Integer key : childColors.keySet()) {
                Integer times = childColors.get(key);

                int oldValue = colorTimes.getOrDefault(key, 0);
                colorTimes.put(key, oldValue + times);
            }
        }

        int maxTimes = 0;

        maxTimes = colorTimes.values().stream().max(Integer::compareTo).get();
        //System.out.println(colorTimes);

        final int temp = maxTimes;
        final Map<Integer, Integer> backupMap = new HashMap<>(colorTimes);

        colorTimes.entrySet().forEach((entry) -> {
            if (entry.getValue() == temp) {
                backupMap.remove(entry.getKey());
            }
        });

       // System.out.println(backupMap);

        for (Integer key : backupMap.keySet()) {
            Integer times = backupMap.get(key);



            for (int i = 0; i < times; i++) {
                if (ret == 0) {
                    ret = key;
                } else {
                    ret ^= key;
                }
            }
        }

        gMax = Math.max(gMax, ret);
        return colorTimes;
    }

    public static void getTreeNodeColors( Node head) {
        int ret = 0;
        Map<Integer, Integer> colorTimes = new HashMap<>();
        Set<Integer> visited = new HashSet<>();

        DFS(head, visited);
        System.out.println(gMax);
        
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Node[] tree = new Node[n];
        int i = 0;

        //System.out.println(tree[0]);
        while (i < n) {
            tree[i] = new Node(i);
            tree[i].color = in.nextInt();
            i++;
        }

        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int indexNode1 = in.nextInt() - 1;
            int indexNode2 = in.nextInt() - 1;
            tree[indexNode1].children.add(tree[indexNode2]);
            tree[indexNode2].children.add(tree[indexNode1]);

        }

        getTreeNodeColors(tree[0]);

    }
}

不能用广度优先遍历，不好保存每个子树的已遍历节点的状态。