树上最短链

结合以上大佬们给出的题解，遍历每一个节点，使用bfs寻找任意两节点的最短路径。题目中增加限制条件：节点要在同一级，所以使用领接表存储每个节点相连的节点。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] grade = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            grade[i] = in.nextInt();
        }
        List> edges = new ArrayList();
        for (int i = 0; i <= n; i++) {
            edges.add(new ArrayList());
        }
        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            // 双向边
            edges.get(u).add(v);
            edges.get(v).add(u);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            min = Math.min(min, bfs(edges, grade, i));
        }
        System.out.println(min == Integer.MAX_VALUE ? -1 : min);
    }
    private static int bfs(List> edges, int[] grade, int st) {
        Queue queue = new LinkedList();
        int n = grade.length;
        boolean[] marked = new boolean[n];
        queue.add(st);
        marked[st] = true;
        int cur = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            cur++;
            while (size-- > 0) {
                int t = queue.poll();
                for (int x : edges.get(t)) {
                    if (marked[x]) continue;
                    if (grade[x] == grade[st])
                        return cur;
                    queue.add(x);
                    marked[x] = true;
                }
            }
        }
        return Integer.MAX_VALUE;
    }
}