트리와 쿼리 15681

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

문제에서 해답을 알려주고 있다
트리는 이차원 ArrayList로 하였고

재귀함수로 탐색하였고 함수 반환할때 subCount라는 배열에 현재 노드를 root로 하는 subtree의 노드개수를 담아서 반환하도록 해서 해결하였다

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

public class Main
{
    static ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
    static int N;
    static int R;
    static int Q;
    static int[] subCount;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        R = Integer.parseInt(input[1]);
        Q = Integer.parseInt(input[2]);

        for(int i = 0; i < N+1; ++i)
            tree.add(new ArrayList<>());

        for(int i = 0; i < N-1; ++i)
        {
            input = br.readLine().split(" ");

            int U = Integer.parseInt(input[0]);
            int V = Integer.parseInt(input[1]);

            tree.get(U).add(V);
            tree.get(V).add(U);
        }
        subCount = new int[N+1];
        recur_makeCount(0, R);


        for(int i = 0; i < Q; ++i)
        {
            int subRootId = Integer.parseInt(br.readLine());
            System.out.println(subCount[subRootId]);
        }
    }

    public static int recur_makeCount(int parent, int nodeId)
    {
        ArrayList<Integer> curNode = tree.get(nodeId);

        subCount[nodeId] = 1;

        for(int child : curNode)
        {
            if(child == parent)
                continue;
            subCount[nodeId] += recur_makeCount(nodeId, child);
        }

        return subCount[nodeId];
    }

}