백준15681 트리와 쿼리

작성일 | In

문제 링크

  • http://icpc.me/15681

문제 출처

  • 2018 연세대학교 컴퓨터과학과 프로그래밍 경진대회 PC번

사용 알고리즘

  • DFS

시간복잡도

  • O(N + Q)

풀이

DFS를 돌면서 Tree DP 비슷한 느낌으로 서브트리의 사이즈를 구해주면 됩니다.

Heavy Light Decomposition(HLD), Centroid Decomposition(CD)등과 같은 알고리즘을 구현할 때 자주 나오기 때문에 알고 넘어가면 좋습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int size[101010];
vector<int> g[101010];

int dfs(int now, int prv){
	size[now] = 1;
	for(auto nxt : g[now]){
		if(prv == nxt) continue;
		size[now] += dfs(nxt, now);
	}
	return size[now];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, r, q; cin >> n >> r >> q;

	for(int i=0; i<n-1; i++){
		int a, b; cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	dfs(r, 0);

	while(q--){
		int t; cin >> t;
		cout << size[t] << "\n";
	}
}