반응형

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

 

15681번: 트리와 쿼리

트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 루트를 기준으로 재귀 함수를 통해 자식 노드들의 개수를 dp 배열에 저장합니다.

 

2. 점화식은 dp[ cur ] += dp[ next ] 입니다.

 

3. return을 할 때 자기 자신도 포함시켜야 하기 때문에 return dp[ cur ] += 1 을 해줍니다.

 

3. 마지막에 dp[num]을 하나씩 출력해주면 됩니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, R, Q;
vector<int> list[100001];
int dp[100001];
int visited[100001];
 
int dfs(int cur)
{
    if (dp[cur] != 0) return dp[cur];
    if (visited[cur] == 1) return 0;
    visited[cur] = 1;
 
    for (auto next : list[cur]) {
        if (visited[next] != 1) {
            dp[cur] += dfs(next);
        }
    }
 
    return dp[cur] += 1;
}
 
int main()
{
    scanf("%d %d %d", &N, &R, &Q);
 
    for (int i = 1; i < N; i++) {
        int U, V;
        scanf("%d %d", &U, &V);
        list[U].push_back(V);
        list[V].push_back(U);
    }
 
    dfs(R);
 
    for (int i = 0; i < Q; i++) {
        int num;
        scanf("%d", &num);
        printf("%d\n", dp[num]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 16933번 - 벽 부수고 이동하기 3 (C++)  (0) 2022.11.16
[ 백준 ] 11758번 - CCW (C++)  (0) 2022.11.15
[ 백준 ] 7682번 - 틱택토 (C++)  (0) 2022.11.13
[ 백준 ] 13913번 - 숨바꼭질 4 (C++)  (0) 2022.11.12
[ 백준 ] 1976번 - 여행 가자 (C++)  (0) 2022.11.11

+ Recent posts

티스토리툴바