BOJ - 15681 ) 트리와 쿼리

---

https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

---

루트노드가 정해졌으므로 루트노드부터 재귀탐색을 하며 

 

하위 노드의 개수를 저장한다. 리프 노드의 경우 1로 간주한다.

 

따라서, 자신과 연결된 노드들의 값 +1을 현재에 값에 저장시키며 재귀탐색을 진행한다.

---

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

public class Main {
	public static int[] cost ;
	public static boolean[] visit ;
	public static ArrayList<Integer> node[];
	public static void main(String[] args) throws Exception {
		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())-1;
		int Q = Integer.parseInt(st.nextToken());
		cost = new int[N];
		visit= new boolean[N];
		node = new ArrayList[N];
		for(int i=0;i<N;i++){node[i] = new ArrayList<>();}
		for(int i=0;i<N-1;i++){
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken())-1;
			int e = Integer.parseInt(st.nextToken())-1;
			node[s].add(e); node[e].add(s);
		}
		DFS(R);
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<Q;i++) {sb.append(1+cost[Integer.parseInt(br.readLine())-1]).append("\n");}
		System.out.println(sb.toString());
	}
	private static int DFS(int now) {
		visit[now] = true;
		for(int i=0;i<node[now].size();i++) {
			if(!visit[node[now].get(i)]) {
				cost[now] += DFS(node[now].get(i));
			}
		}
		return cost[now]+1;
	}
}

---