[dp/dfs] 백준 15691번

루트가 있는 트리에서 각 노드 이하로 몇 개의 노드가 있는지 카운트해야한다.

처음 문제를 봤을때 쉽게 생각했는데 시간초과/메모리초과 문제로 꽤나 오래 걸렸다. 

 

dfs를(재귀를) 이렇게 활용할 수 있구나 깨달아서 좋은 문제

 

import sys
sys.setrecursionlimit(10**5)

N, R, Q = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
dp = [0 for _ in range(N+1)]

for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(x):
    dp[x]=1
    for next in graph[x]:
        if not dp[next]:
            dfs(next)
            dp[x] += dp[next]
dfs(R)
for _ in range(Q):
    print(dp[int(sys.stdin.readline())])

[**] 이때 sys.setrecursionlimit 제대로 걸어야 한다. .. 안그러면 메모리초과,,,