[백준] 15681 트리와 쿼리

문제링크: www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

너무 많이 풀어본 유형이라 쉬웠다. 문제 설명이 아주 구체적이어서 그래프와 트리의 개념을 이해하기에 좋고, 그것을 실습 해보는 목적으로 풀기에 좋은 문제인 것 같다. 

import java.io.*;
import java.util.*;

public class Main {
	public static int N,R,Q;
	public static ArrayList<Integer> []adj;
	public static int ans[];
	public static boolean []visited;
	public static int dfs(int cnode){
		int ret = 1;
		for(int i=0;i<adj[cnode].size();i++){
			int nnode = adj[cnode].get(i);
			if(visited[nnode]) continue;
			visited[nnode] = true;
			ret+= dfs(nnode);
		}
		return ans[cnode] = ret;
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());
		adj = new ArrayList[N+1];
		ans = new int[N+1];
		visited = new boolean[N+1];
		for(int i=1;i<=N;i++){
			adj[i] = new ArrayList<Integer>();
		}
		for(int i=1;i<=N-1;i++){
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			adj[s].add(e);
			adj[e].add(s);
		}
		visited[R] = true;
		dfs(R);
		for(int i=0;i<Q;i++){
			int query = Integer.parseInt(br.readLine());
			System.out.println(ans[query]);
		}
	}

}