[BaekJoon] 15591번 : MooTube

15591번 : MooTube

문제가 복잡해서 읽는데만 시간이 오래 걸렸다..

주절주절 길지만 정리 해보자면 [1, 2] 가 주어지는 경우 2번 노드에서 유사도가 1 이상인 모든 노드의 개수를 출력한다.

유사도는 A 노드와 B 노드를 잇는 간선 중 가장 작은 간선의 무게를 가지게 된다.

만약 이렇게 생긴 그래프가 있는 경우 1과 3의 유사도는 2가 된다.

1과 3을 잇는 간선 중 가장 작은 간선의 무게는 2이기 때문이다.

마찬가지로 1과 4의 유사도는 3이 된다.

노드간 유사도를 구하는 방법은 노드간 거리를 구하는 방법을 약간 변형하면 된다.

예를 들어 1과 4의 거리를 구하고 싶은 경우 3 + 4 의 계산을 하게 된다.

이때 더하기 계산을 하지 말고 거리를 최솟값으로 갱신 해주면 된다.

---

import sys
from collections import deque


def BFS(N, graph, k, start):
	visit = [False] * (N + 1)
	queue = deque([[start, float('inf')]])
	visit[start] = True

	answer = 0
	while queue:
		node, USADO = queue.popleft()
		for i in graph[node]:
			visit_node, visit_USADO = i

			min_USADO = min(USADO, visit_USADO)
			if not visit[visit_node] and min_USADO >= k:
				answer += 1
				visit[visit_node] = True
				queue.append([visit_node, min_USADO])

	return answer


if __name__ == "__main__":
	N, Q = map(int, input().split())
	graph = {i + 1: [] for i in range(N)}

	for _ in range(N - 1):
		start, end, USADO = map(int, sys.stdin.readline().rsplit())
		graph[start].append([end, USADO])
		graph[end].append([start, USADO])

	for _ in range(Q):
		k, check = map(int, sys.stdin.readline().rsplit())
		print(BFS(N, graph, k, check))