c++ 15681번 트리와 쿼리 (백준)

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

vector<int> vec[100001]; //간선 저장용
vector<int> dp; //dp용
vector<bool> v; //방문처리용

void loop(int r) { //DFS
	for(int x : vec[r]) {
		if(!v[x]) {
			v[x] = true; //방문처리
			loop(x);
			dp[r] += dp[x];
		}
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, r, q;
	cin >> n >> r >> q;
	dp.assign(n+1, 1);
	v.assign(n+1, false);
	
	for(int i=1; i<n; i++) { //간선 입력받기
		int a, b;
		cin >> a >> b;
		vec[a].emplace_back(b);
		vec[b].emplace_back(a);
	}
	
	v[r] = true; //방문처리
	loop(r); // DFS 시작

	while(q--) { //출력
		int a;
		cin >> a;
		cout << dp[a] << '\n';
	}

}

 

풀이 : DFS

 

DFS를 재귀호출을 이용하여 구현했습니다. c언어로 구현하기엔 실력이 딸려서 STL을 사용했습니다.

 

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

15681번: 트리와 쿼리