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

15681번 : 트리와 쿼리

---

문제)

간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.

• 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.

만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.

 

 

 

입력 :

트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)

이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)

이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다.

이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N)

입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.

 

 

 

출력 :

Q줄에 걸쳐 각 쿼리의 답을 정수 하나로 출력한다.

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n, r, q;
vector<vector<int>> vec;
int sz[100010];
 
int dfs(int cur, int prv)
{
    // 기본적으로 현재노드는 자기 자신 하나를 가지고 있음
    sz[cur] = 1;
 
    for (auto nxt : vec[cur])
    {
        if (nxt == prv) continue;
 
        // 현재 노드에 자식 노드들의 갯수를 더해준다.
        sz[cur] += dfs(nxt, cur);
    }
 
    // sz[cur]를 리턴한다.
    return sz[cur];
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> r >> q;
    vec.resize(n + 1, vector<int>());
 
    int a, b;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
 
    // 루트를 기반으로 sz를 채워 넣는다.
    dfs(r, -1);
 
    for (int i = 0; i < q; i++)
    {
        cin >> a;
        cout << sz[a] << "\n";
    }
 
    return 0;
}
 

---

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

15681번: 트리와 쿼리