[BOJ] Q15681 트리와 쿼리 성공

[BOJ] Q15681 트리와 쿼리 성공

Question

Language: Python

Difficulty: Gold 3~4

q2533와 같은 방식으로 접근해서 풀이할 수 있다.

대신, 점화식은 아래와 같이 활용하면된다. 매번의 dfs를 수행하고 나면 해당 노드의 정점 개수를 반환하도록 한다, 리프 노드의 값은 항상 1이다.

size[vertex]+=dfs(child)

Solution

import sys
def dfs(vertex):
    global size,visited
    visited[vertex]=True

    for child in graph[vertex]:
        if visited[child]:
            continue
        size[vertex]+=dfs(child)
    
    return size[vertex]

if __name__ == "__main__":
    sys.setrecursionlimit(10**5)
    n_vertex,root,n_queries=map(int,input().split())
    graph=[[] for _ in range(n_vertex+1)]
    visited=[False]*(n_vertex+1)
    for _ in range(n_vertex-1):
        v1,v2=map(int,input().split())
        graph[v1].append(v2)
        graph[v2].append(v1)
    queries=[int(input()) for _ in range(n_queries)]
    size=[1]*(n_vertex+1)
    dfs(root)
    for query in queries:
        print(size[query])