문제

풀이과정

완전 탐색 문제.
처음에는 간선배열을 만들어, 미리 만든 후, 모든 노드간의 USADO 값을 찾아낸 후, K, V 에 대한 값들을 찾았더니, 메모리 초과가 나오더라. 아마 N 만큼의 이차원배열을 만들어서 그런듯 하여, 인접 리스트로 정리하여 다시 식을 구했다. 하지만 역시, 시간 초과.
어떠 부분이 문제인지 확인해보니, 간선 값을 찾는 과정없이 바로 BFS 탐색을 한다. 어차피 두 쌍 사이의 USADO 값은 그 경로의 모든 연결의 USADO 값 가운데 최솟값이 되기 때문에, K 값 보다 작은 경우라면, 최솟값을 찾았을 때 어차피 범위안에 들어오지 못하게 되므로 K 보다 이상인 애들만 카운트 함으로써 시간 초과를 해결하였다.

약간 최단 경로 알고리즘 (다익스트라)과 매우 비슷하다는 생각을 하게 되었다.

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N,Q;
    static class Node {
        int next;
        int weight;

        public Node(int next, int weight) {
            this.next = next;
            this.weight = weight;
        }
    }
    static List<Node> adjList[];

    static boolean[] visited;
    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());

        adjList = new ArrayList[N+1];
        for(int i=1; i<=N; i++) {
            adjList[i] = new ArrayList();
        }

        for(int i=0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int usado = Integer.parseInt(st.nextToken());

            adjList[a].add(new Node(b,usado));
            adjList[b].add(new Node(a,usado));
        }


        StringBuilder sb = new StringBuilder();
        while(--Q>=0) {
            st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            visited = new boolean[N+1];
            sb.append(BFS(V,K)).append("\n");
        }
        System.out.println(sb.toString());
    }

    private static int BFS(int st, int K) {
        Queue<Integer> q = new LinkedList<>();
        q.add(st);
        visited[st] = true;
        int cnt = 0;

        while(!q.isEmpty()) {
            int curr = q.poll();
            for(Node nNode : adjList[curr]) {
                if(visited[nNode.next]) continue;
                if(nNode.weight<K) continue;
                visited[nNode.next]=true;
                q.add(nNode.next);
                cnt++;
            }
        }

        return cnt;
    }
}