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

https://www.acmicpc.net/problem/15681

힌트를 보지 않고 dfs와 bfs를 사용하여 푼 문제
bfs로 그래프를 탐색해 각 노드의 층수를 정해주고
dfs로 각 그래프의 자식들의 정점수를 탐색하여 풀었다.

처음에는 dp를 쓰지 않고 풀었다가 탐색한 노드를 나타내는 visit배열의 초기화를 해주려면 시간복잡도가 O(n^2)가 나온다는 사실을 알아버려서 dp로 선회

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> graph[100001];
int visited[100001];
bool visit[100001];
int dp[100001];
void bfs(int n);
int dfs(int n);
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, r, q;
    cin >> n >> r >> q;
    for(int i=0; i<n-1; i++){
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    bfs(r);
    dfs(r);
    for(int i=0; i<q; i++){
        int x;
        cin >> x;
        cout << dp[x] << '\n';
    }
    return 0;
}
void bfs(int n){
    queue<int> q;
    q.push(n);
    visited[n] = 1;
    while(!q.empty()){
        int x = q.front();
        for(int i=0; i<graph[x].size(); i++){
            if(!visited[graph[x][i]]){
                visited[graph[x][i]] = visited[x]+1;
                q.push(graph[x][i]);
            }
        }
        q.pop();
    }
}
int dfs(int n){
    visit[n] = true;
    int S = 1;
    for(int i=0; i<graph[n].size(); i++){
        if(!visit[graph[n][i]] && visited[n]<visited[graph[n][i]]){
            S += dfs(graph[n][i]);
        }
    }
    dp[n] = S;
    return S;
}
                                                         ```