15591. Mootube

처음에 MST인가? 라는 생각을 가졌는데 결국 이문제는 탐색을 해야하는 문제이다. 주어진 노드 관점에서 bfs를 진행해야 유사도를 측정해서 개수를 셀 수 있다.

 

유사도라는 것을 모든 연결들의 유사도중의 최솟값으로 정했으므로 노드와 노드사이의 거리가 k보다 작다면 방문자체를 할 필요가 없다.

import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)
def bfs(start, k):
  global graph
  visited = [False] * (N+1)
  q = deque()
  q.append(start)
  count = 0
  while q:
    now = q.popleft()
    visited[now] = True
    for n_n, w in graph[now]:
      if not visited[n_n] and w >= k:
        q.append(n_n)
        count += 1
  return count
N, Q = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  graph[b].append((a, c))

for _ in range(Q):
  k, v = map(int, input().split())
  print(bfs(v, k))