[백준 15681] 트리와 쿼리 C++

15681번: 트리와 쿼리

트리에서의 다이나믹 프로그래밍 입문 #1

 

R이 트리의 기본 루트일 때 정점 U를 루트로 하는 Subtree에 속한 정점의 수를 출력

 

오징어같아

문제 이해를 위한 설명!

 

트리의 기본 루트는 5이다

사진에서 4를 루트로 하는 서브트리는 아래와 같다

작은 오징어

그림과 같이 4를 루트로하는 서브트리의 정점은 1, 2, 3, 4 이다 (자신도 서브트리에 물론 포함)

 

트리의 리프노드 까지 가면 dp[now]를 반환한다(dp[i]의 초기값은 모두 1)

dp[now] 는 now노드와 연결된 자식노드들의 개수가 되도록 

dp[now] += dfs(next); 코드를 작성해준다

#include <bits/stdc++.h>
 
using namespace std;
 
int N, R, Q;
vector<int> query, tree[100001];
bool visited[100001];
int dp[100001];
 
int dfs(int now){
    visited[now] = true;
    
    for(int i = 0; i < tree[now].size(); i++){
        int next = tree[now][i];
        if(visited[next]) continue;
        dp[now] += dfs(next);
    }
    
    return dp[now];
}
 
void input(){
    int u, v, q;
    cin >> N >> R >> Q;
    for(int i = 0; i < N-1; i++){
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for(int i = 0; i < Q; i++){
        cin >> q;
        query.push_back(q);
    }
    for(int i = 0; i <= N; i++){
        dp[i] = 1;
    }
}
 
int main(){
    input();
    dfs(R);
    
    for(auto w : query){
        cout << dp[w] <<  "\n";
    }
    
    return 0;
}

DFS, 양방향 트리, DP의 가장 기본적인 성질들이 섞인 문제