[백준] 15681 트리와 쿼리

15681번: 트리와 쿼리

fast io 미적용

문제 확인

 

트리 dp 문제입니다.

 

풀이

 

그래프를 입력받아서 작성하고 dfs를 통해 dp 값을 채워 넣어주면 됩니다.

자신을 포함하여 서브트리의 정점 개수이므로 초기값은 1로 설정을 하고 자식들의 dp값을 합쳐주면 결과를 얻어낼 수 있습니다.

for(auto child : cur.edge)

   if(child != prev)

      dp[cur] += dfs(child, cur);

prev 값은 되돌아가는 것을 방지하기 위함이며 트리이기 때문에 사이클이 없으므로 visited를 대신합니다.

 

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
typedef struct vtx {
    int dp;
    vector<int>edge;
}vtx;
vtx gph[100001];
int dfs(int i, int prev) {
    vtx &cur = gph[i];
    cur.dp = 1;
    for (auto next : cur.edge)
        if (next != prev)
            cur.dp += dfs(next, i);
    return cur.dp;
}
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, r, q;
    cin >> n >> r >> q;
 
 
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        gph[a].edge.push_back(b);
        gph[b].edge.push_back(a);
    }
 
    dfs(r, 0);
    while (q--) {
        int u;
        cin >> u;
        cout << gph[u].dp << '\n';
    }
}