[Baekjoon,15681] 트리와 쿼리

트리 구조에서 DP를 이용하여 해결하는 문제이다. 주어진 정점을 서브트리로 했을 때 서브 트리의 정점의 개수를 반환하여야 한다. 이를 구현하기 위해서 루트에서 부터 DFS를 하였다. 서브트리의 정점 개수만 구하면 되므로 따로 트리구조를 형성하지 않아도 된다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAX=100001;

int V,R,Q;
vector<int> adj[MAX];
// treeSize[r] = 루트가 r인 트리가 가진 정점의 개수
int treeSize[MAX];

int dfs(int root)
{
    int& ret=treeSize[root];
    // 이미 방문한 정점인 경우 
    if(ret!=-1)
        return 0;
    
    ret=1;
    for(int i=0;i<adj[root].size();++i)
    {
        int there=adj[root][i];
        ret+=dfs(there);
    }
    return ret;
}

int main()
{
    cin>>V>>R>>Q;
    for(int i=0;i<V-1;++i)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    memset(treeSize,-1,sizeof(treeSize));
    dfs(R);
    
    for(int i=0;i<Q;++i)
    {
        int n;
        scanf("%d",&n);
        printf("%d \n",treeSize[n]);
    }
    return 0;
}