문제

https://www.acmicpc.net/problem/15591

Input)
4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1
Output)
3
0
2

Point

set

• set 자료구조를 사용하면 list보다 시간복잡도에서 이득이 있다.
• 삭제, 탐색(in) 연산

tree

• 간선이 n-1개고 모든 node사이에 하나의 경로 존재
  : tree

변수

• usd : 두 node사이의 유사도

BFS

• 시작 node를 고정하고, 모든 node간의 usd계산
• 현재 node의 usd : 여태까지 거쳐온 간선들(usd) 중 최소값
• 현재 node에서 다음 node로 BFS를 뻗어 나갈 때,
  다음 node의 usd : 현재 node의 usd와, 그 간선의 usd 중 최소값

전체코드

from collections import deque

n, q = [int(x) for x in input().split()]

tree = [[] for _ in range(n+1)]
usd = [[0]*(n+1) for _ in range(n+1)]

for i in range(n-1):
  a, b, u = [int(x) for x in input().split()]
  tree[a].append(b)
  tree[b].append(a)
  usd[a][b] = u
  usd[b][a] = u


que = deque()
def get_usd(k, s):
  global usd
  global que
  vis = set()
  count = 0
  
  que.append(s)
  vis.add(s)
  usd[s][s] = 1000000000
  while(que):
    cur = que[0]
    que.popleft()
    for a in tree[cur]:
      if a not in vis:
        usd[s][a] = min(usd[s][cur], usd[cur][a])
        if usd[s][a] >= k:
          count += 1
        que.append(a)
        vis.add(a)
  usd[s][0] = 1
  return count

def check_num(k, s):
  if usd[s][0]==1:
    count = -1
    for a in usd[s][1:]:
      if a >= k:
        count += 1
    return count
  else:
    return get_usd(k, s)

for i in range(q):
  k, s = [int(x) for x in input().split()]
  print(check_num(k, s))