백준 15591

문제

Code

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class P15591 {
	static class Node {
		int end;
		int weight; 

		Node(int end, int weight) {
			this.end = end;
			this.weight = weight;
		}
	}
	static ArrayList<ArrayList<Node>> list;
	static boolean[] visited;
	static int[][] query;
	static StringBuilder sb = new StringBuilder();
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());

		list = new ArrayList<>();
		visited = new boolean[N + 1];
		query = new int[Q][2];

		for(int i = 0; i <= N; i++) {
			list.add(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 w = Integer.parseInt(st.nextToken());

			list.get(a).add(new Node(b, w));
			list.get(b).add(new Node(a, w));
		}

		for(int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int k = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			query[i][0] = k; 
			query[i][1] = v; 
		}
		bfs();
		
		
		bw.write(sb.toString());
		br.close();
		bw.flush();
		bw.close();
	}
	private static void bfs() {
		Queue<Integer> q;
		for(int i = 0; i < query.length; i++) {
			int k = query[i][0];
			int v = query[i][1];
			
			Arrays.fill(visited, false);
			visited[v] = true;
            
			q = new LinkedList<>();
			q.add(v);
			
			int count = 0;
			while(!q.isEmpty()) {
				int now = q.poll();
				
				for(Node node : list.get(now)) {
					if(!visited[node.end] && node.weight >= k) {
						q.add(node.end);
						visited[node.end] = true;
						count++;
					}
				}
			}
			sb.append(count).append('\n');
		}
	}

}