[BOJ 15681 | C++] 트리와 쿼리 :: Tree DP

• 문제 링크 : https://www.acmicpc.net/problem/15681
• 문제 태그 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색. 트리에서의 다이나믹 프로그래밍

 

풀이

DFS를 통해 방문한 노드의 개수를 누적합니다. 그리고 더 이상 방문할 정점이 없을 때 재귀를 빠져나오면서 지나온 경로를 따라 방문한 정점의 개수를 더해 해당 트리에 속한 노드의 개수를 업데이트합니다.  

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

int n;
vector<int>dp;
vector<bool>seen;
vector<vector<int>>g;

void dfs(int cur) {
    if (seen[cur]) return;
    seen[cur] = true;
    dp[cur] = 1;

    for (auto nxt : g[cur]) {
        if (seen[nxt]) continue;
        dfs(nxt);
        dp[cur] += dp[nxt];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int r, q;
    cin >> n >> r >> q;

    dp.resize(n + 1, 0);
    g.resize(n + 1);
    seen.resize(n + 1, false);

    for (int i = 0;i < n - 1;i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(r);

    while (q--) {
        int u;
        cin >> u;
        cout << dp[u] << '\n';
    }
}