https://www.acmicpc.net/problem/15681
15681번: 트리와 쿼리
트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)
www.acmicpc.net
1. 현재정점(r) 을 기준으로 각 자식갯수 + 자신 으로 dp를 구성하였다.
import sys
sys.setrecursionlimit(10**6)
n, r, q = map(int, input().split())
graph = [[] for _ in range(n+1)]
dp = [0 for _ in range(n+1)]
def dfs(x):
dp[x] = 1
for next in graph[x]:
if not dp[next]:
dfs(next)
dp[x] += dp[next]
for _ in range(n-1):
x, y = map(int, sys.stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
dfs(r)
for _ in range(q):
print(dp[int(sys.stdin.readline())])
댓글