BOJ 15681 트리와 쿼리

1 개요

BOJ 15681 트리와 쿼리

• 백준 온라인 저지 15681번 문제
• BOJ 38단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N, R, Q;
vector<int> e[100001];
bool visited[100001];
int nums[100001];

int dfs(int r) {
    if (nums[r] != 0) return nums[r];
    visited[r] = true;
    int cnt = 1;
    for (int i=0; i<e[r].size(); i++){
        int next = e[r][i];
        if (visited[next]) continue;
        cnt += dfs(next);
    }
    nums[r] = cnt;
    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> R >> Q;
    int U, V;
    for (int i=0; i<N-1; i++) {
        cin >> U >> V;
        e[U].push_back(V);
        e[V].push_back(U);
    }
    dfs(R);
    for (int i=0; i<Q; i++){
        cin >> U;
        cout << nums[U] << '\n';
    }
}