网易2023.9.23笔试第四题

提供一点小小的思路，广度优先

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int q = scan.nextInt();
        boolean[][] flag = new boolean[n + 1][n + 1];
        for (int i = 1; i < n; i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            flag[x][y] = true;
            flag[y][x] = true;
        }
        for (int i = 0; i < q; i++) {
            boolean[] visited = new boolean[n + 1];
            int m = scan.nextInt();
            int res = 1;
            Set<Integer> set = new HashSet<>();
            int t1 = scan.nextInt();
            set.add(t1);
            for (int j = 1; j < m; j++) {
                int t = scan.nextInt();
                set.add(t);
            }
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(t1);
            visited[t1] = true;
            int c = 0;  //用来记录是不是访问的起始点
            while (!queue.isEmpty()) {
                int t = queue.poll();
                c++;
                int count = 0;
                for (int j = 1; j < n + 1; j++) {
                    if (flag[t][j] && !visited[j]) {
                        visited[j] = true;
                        queue.offer(j);
                        if (set.contains(j)) {
                            count++;
						  //如果是访问的起始点，则与t点直连的点要大于2才会让访问次数+1
                            if (count > (c > 1 ? 1 : 2)) { 
                                res++;
                            }
                        }
                    }
                }
            }
            System.out.println(res);
        }
    }
}

顺便引个流https://www.nowcoder.com/feed/main/detail/ca97983c53004dd6a614f26e9d87d257