15681_트리와쿼리

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

15681번: 트리와 쿼리

 

 

 

트리 구조를 받아온 후에, dfs로 노드를 후위순위하면서 뒤에서부터 서브트리의 개수를 더해주면 된다.

 

각 자식트리의 서브트리를 더해주는 형태라고 생각하면 된다.

 

처음에 bfs를 사용해서 그때 그때 개수를 구했는데그러며 시간초과가 나니 생각해두면 될 것 같다.

 

import sys
from collections import deque
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

n,r,Q = map(int,input().split())
graph = [ [] for _ in range(n+1) ]
for _ in range(n-1):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

def cnt(node):
    count[node] = 1
    for i in graph[node]:
        if not count[i]:
            cnt(i)
            count[node] += count[i]

count = [0] * (n+1)
cnt(r)
for _ in range(Q):
    print(count[int(input())])