풀이

BFS방식으로 풀이한다.
경로에 유사도가 k보다 작은 값을 포함시키면, 해당 경로로 이어진 영상들의 유사도는 k보다 작아지므로, 큐에 포함시키는 영상의 조건은 <방문한적이 없고, 유사도가 k보다 크거나 같다> 이다.

코드

package BOJ;

import java.io.*;
import java.util.*;

public class sol15591 {
    static int n, q;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());

        ArrayList<Video>[] graph = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int usado = Integer.parseInt(st.nextToken());
            graph[start].add(new Video(end, usado));
            graph[end].add(new Video(start, usado));
        }

        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            System.out.println(bfs(start, k, graph));
        }
    }

    public static int bfs(int start, int k, ArrayList<Video>[] graph) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        int count = 0;

        visited[start] = true;
        q.add(start);

        while (!q.isEmpty()) {
            int curr = q.poll();
            for (Video next : graph[curr]) {
                if (!visited[next.num] && next.usado >= k) {
                    count++;
                    q.add(next.num);
                    visited[next.num] = true;
                }
            }
        }
        return count;
    }


    public static class Video {
        int num;
        int usado;

        Video(int num, int usado) {
            this.num = num;
            this.usado = usado;
        }
    }
}