[문제]
간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자. 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다. 만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.
[입력]
트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) 이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다. 이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N) 입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.
[출력]
Q줄에 걸쳐 각 쿼리의 답을 정수 하나로 출력한다.
[소스]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class boj15681 {
static List<Integer>[] list, tree;
static int parent[],size[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine()," ");
int N = Integer.parseInt(stk.nextToken()); // 정점의 수
int R = Integer.parseInt(stk.nextToken()); // 루트의 번호
int Q = Integer.parseInt(stk.nextToken()); // 쿼리의 수
list = new ArrayList[N+1];
tree = new ArrayList[N+1];
parent = new int[N+1];
size = new int [N+1];
for(int i=0;i<list.length;i++) {
list[i]=new ArrayList<>();
tree[i]=new ArrayList<>();
}
for(int i=0;i<N-1;i++) {
stk = new StringTokenizer(br.readLine()," ");
int U = Integer.parseInt(stk.nextToken());
int V = Integer.parseInt(stk.nextToken());
list[U].add(V);
list[V].add(U);
}
makeTree(R,-1); // 트리생성
countSubtreeNodes(R);
for(int i=0;i<Q;i++) {
int query = Integer.parseInt(br.readLine());
System.out.println(size[query]);
}
}
public static void makeTree(int currentNode, int parentNode) {
for(int node : list[currentNode]) {
if(node!=parentNode) {
tree[currentNode].add(node);
parent[node] = currentNode;
makeTree(node, currentNode);
}
}
}
public static void countSubtreeNodes(int currentNode) {
size[currentNode]=1;
for(int node : tree[currentNode]) {
countSubtreeNodes(node);
size[currentNode]+=size[node];
}
}
}