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

문제

백준 15681

15681번: 트리와 쿼리

풀이

리프 노드는 자식이 없으므로 서브 트리의 정점 개수는 자기 자신 1개입니다.

따라서 dp 배열을 1로 초기화해줍니다.

루트 노드부터 dfs를 실행하고, 서브 트리의 탐색이 모두 끝났다면 부모에게 자신의 서브 트리 값을 더해줍니다.

부모가 -1인 경우는 루트 노드이므로 더하지 않습니다.

예제를 보겠습니다.

숫자는 해당 정점에서의 서브 트리의 정점 개수이고, 괄호 안은 방문 순서입니다.

C++ 기준 ios_base::sync_with_stdio, cin.tie 등으로 입출력을 빠르게 해주지 않으면 시간 초과가 납니다.

소스 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

#include<iostream> #include<vector> using namespace std;   int dp[100001]; bool visited[100001]; vector<int> v[100001]; bool isleaf; int N, R, Q;   void dfs(int node, int parent) {     visited[node] = true;     for (int i = 0; i < v[node].size(); i++)     {         int next = v[node][i];         if (visited[next])             continue;         dfs(next, node);     }     if (parent != -1)     {         dp[parent] += dp[node];     } } int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     fill_n(dp, 100001, 1);     cin >> N >> R >> Q;     int a, b;     for (int i = 0; i < N-1; i++)     {         cin >> a >> b;         v[a].push_back(b);         v[b].push_back(a);     }     dfs(R, -1);     for (int i = 0; i < Q; i++)     {         int q;         cin >> q;         cout << dp[q] << '\n';     }     return 0; } Colored by Color Scripter

cs