神秘的苹果树

import java.util.*;
public class Main {
	public static void main(String[] args) {
		// 因为是不成环的图所以边数为节点数 - 1
		Scanner sc = new Scanner(System.in);
		int nodeNum = sc.nextInt();

		// 先使用ColorNode[]来存储所有结点并构建：无向无权不成环的图
		ColorNode[] nodes = new ColorNode[nodeNum + 1];
		for (int i = 0; i < nodeNum - 1; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();

			if (nodes[u] == null) {
				nodes[u] = new ColorNode();
			}
			if (nodes[v] == null) {
				nodes[v] = new ColorNode();
			}
			nodes[v].subTree.add(nodes[u]);
			nodes[u].subTree.add(nodes[v]);
		}

		// 无向图变为有向图
		modify(nodes[1]);

		sc.nextLine();
		// 设置颜色
		String[] split = sc.nextLine().split(" ");
		for (int i = 1; i <= nodeNum; i++) {
			nodes[i].color = Integer.valueOf(split[i - 1]);
		}

		// 记录开始的结点编号
		int loop = sc.nextInt();
		int[] res = new int[loop];
		int[] opNum = new int[loop];
		sc.nextLine();
		for (int i = 0; i < loop; i++) {
			opNum[i] = Integer.valueOf(sc.nextLine());
		}

		// 遍历要操作的结点
		for (int i = 0; i < loop; i++) {
			int opeNode = opNum[i];

			// 深搜并将结果保存在map中
			HashMap<Integer, Integer> map = new HashMap<>();
			dfs(nodes[opeNode], map);

			// 按照value降序排序
			List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
			Collections.sort(list, (Map.Entry<Integer, Integer> entry1, Map.Entry<Integer, Integer> entry2) -> {
				return entry2.getValue() - entry1.getValue();
			});

			// 找到符合要求的颜色
			int curRes = list.get(0).getKey();
			int curMaxNum = list.get(0).getValue();
			int j = 1;
			// 如果出现重复的最大数量颜色编号，则找到最小的那个
			while (j < list.size() && list.get(j).getValue() == curMaxNum) {
				curRes = list.get(j).getKey() < curRes ? list.get(j).getKey() : curRes;
				j++;
			}
			// 保存结点
			res[i] = curRes;
		}

		// 打印结果
		for (int i = 0; i < res.length; i++) {
			System.out.println(res[i]);
		}

	}

	// 深搜：类似前序遍历
	public static void dfs(ColorNode root, HashMap<Integer, Integer> map) {
		if (root == null)
			return;

		int color = root.color;
		Integer aDefault = map.getOrDefault(color, -1);
		if (aDefault == -1) {
			// 说明当前颜色第一次被检测到
			map.put(color, 1);
		} else {
			map.put(color, aDefault + 1);
		}
		for (ColorNode subNode : root.subTree) {
			dfs(subNode, map);
		}
	}

	// 从无向树变为有向树(层序遍历)
	public static void modify(ColorNode root) {
		ArrayDeque<ColorNode> deque = new ArrayDeque<>();
		deque.addLast(root);

		while (deque.size() != 0) {
			int size = deque.size();
			for (int i = 0; i < size; i++) {
				ColorNode first = deque.removeFirst();
				for (ColorNode curSub : first.subTree) {
					deque.addLast(curSub);
					curSub.subTree.remove(first);
				}
			}
		}

	}

	static class ColorNode {
		int color;
		ArrayList<ColorNode> subTree;

		public ColorNode() {
			this.color = -1;
			this.subTree = new ArrayList<>();
		}
	}
}