백준 15681

문제

---

dp[N]

R을 루트노드로 갖는 트리에서,
N + 1 번째 노드를 루트노드로 가지는 서브트리의 정점의 개수 저장
(인덱스를 0부터 썼기 때문에 +1을 해주었다)

countSubTreeNodes(int node)

node + 1 번째 노드를 루트노드로 갖는 트리의 각 정점들에 대해

각 정점을 루트노드로 갖는 서브트리의 정점의 개수를 dp 에 저장

이 때, '서브트리 내의 정점의 개수'만 세야함

따라서 인접 리스트 상으로는 서브트리의 루트노드의 부모노드는 연결되어있지만

카운팅하면 안되므로 주의

정점부터 아래로 탐색하는데, 이미 지나온 부모 노드는

정점의 개수를 셀 때 + 0 이 되도록 함.

ex) 위에서 4를 루트로 갖는 서브트리를 고려해야하는데

인접리스트 상으로는 4와 5가 연결되어있지만 5는 카운팅하면 안된다.

---

Code

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class P15681 {

	static ArrayList<ArrayList<Integer>> tree;
	static Integer[] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		
		dp = new Integer[N];
		tree = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			tree.add(new ArrayList<>());
		}
		for(int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		countSubTreeNodes(R - 1);
		
		int U;
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < Q; i++) {
			U = Integer.parseInt(br.readLine());
			sb.append(dp[U - 1]).append('\n');
		}
		System.out.println(sb.toString());
	}
	private static int countSubTreeNodes(int node) {
		if(dp[node] != null) {
			return 0;
		}
		dp[node] = 1;
		for(int next : tree.get(node)) {
			dp[node] += countSubTreeNodes(next);
		}
		return dp[node];
	}

}