BFS：100% public class Main5 { static List<Integer>[] edges; static boolean[] vis; static int n; static int[] val; // 贪心，从最小的节点出发,dfs，且最小节点值只能有1个 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for (int j = 0; j < t; ++j) { n = scanner.nextInt(); // 节点编号1-n edges = new List[n + 1]; vis = new boolean[n + 1]; for (int i = 0; i <= n; i++) { edges[i] = new ArrayList<>(); } int[] a = new int[n - 1]; int[] b = new int[n - 1]; for (int i = 0; i < n - 1; i++) { a[i] = scanner.nextInt(); } for (int i = 0; i < n - 1; i++) { b[i] = scanner.nextInt(); } for (int i = 0; i < n - 1; i++) { edges[a[i]].add(b[i]); edges[b[i]].add(a[i]); } val = new int[n + 1]; int minVal = Integer.MAX_VALUE; int minNode = 0; for (int i = 1; i <= n; i++) { int x = scanner.nextInt(); if (x < minVal) { minVal = x; minNode = i; } val[i] = x; } Queue<Integer> queue = new LinkedList<>(); queue.offer(minNode); vis[minNode] = true; boolean flag = true; while (!queue.isEmpty() && flag) { int size = queue.size(); for (int i = 0; i < size; i++) { int p = queue.poll(); for (int child : edges[p]) { if (vis[child]) { continue; } if (val[child] <= val[p]) { flag = false; break; } queue.offer(child); vis[child] = true; } if (!flag) { break; } } } System.out.println(flag ? minNode : -1); } } }