[ 백준 BOJ ] 15681번 - 트리와 쿼리 (C++)

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

 

 

생각 흐름

• 문제를 이해하는 것부터 어려웠다. R로부터 트리 형식으로 만들었을 때 주어지는 정점 U 아래에 서브트리의 정점의 개수를 세는 문제이다.
• 정점의 개수를 세야하므로 R로부터 시작해서 각 노드들을 방문하며 각 노드에 대해 서브 트리의 정점의 개수를 세준다.
• 한 노드에서 각 하위 노드에서의 서브 트리 노드의 개수를 세야하므로 재귀를 사용했다.
• 재귀에서 주의해야 할 점은 parentNode를 주어줘서 역방향으로 가지 않도록 해야한다.

 

 

#include <iostream>
#include <vector>

#define endl '\n'

using namespace std;

int N, R, Q;
vector<int> edge[100001];
int ans[100001];
int query[100001];

int solve(int parentNode, int nowNode){
    int sum = 0;
    
    for(int i = 0; i<edge[nowNode].size(); i++){
        if(edge[nowNode][i]==parentNode){
            continue;
        }
        
        sum += solve(nowNode, edge[nowNode][i]);
    }
    sum++;
    ans[nowNode] = sum;
    return sum;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N>>R>>Q;
    
    for(int i = 0; i<N-1; i++) {
        int U,V;
        cin>>U>>V;
        edge[U].push_back(V);
        edge[V].push_back(U);
    }
    
    solve(-1, R);
        
    for(int i = 0; i<Q; i++){
        cin>>query[i];
    }
    
    for(int i = 0; i<Q; i++){
        cout<<ans[query[i]]<<endl;
    }
    
    return 0;
}