BOJ 15681: 트리와 쿼리

#BOJ 15681: 트리와 쿼리

15681번: 트리와 쿼리

#풀이

트리의 루트노드를 알려주고 서브트리의 정점의 개수를 구하는 문제이다.

 

맨 처음엔 BFS를 사용하여 정점을 입력 받을 때 마다 직접 구했는데 시간초과가 떠서  

DFS를 이용하여 서브 트리의 개수를 구할 수 있었다.

 

재귀를 이용하여 DFS를 하면 쉽게 서브트리의 정점의 개수를 구할 수 있다.

 

#코드

#include<iostream>
#include<vector>

using namespace std;
int n, r, q;
vector<int>adj[100001];
int prt[100001];
int subTree[100001];
bool vis[100001];
int dfs(int cur) {
	vis[cur] = 1;
	for (auto nxt : adj[cur])
	{
		if (vis[nxt] == 1)
			continue;
		subTree[cur] += dfs(nxt);

	}
	subTree[cur]++;
	return subTree[cur];
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> r >> q;
	prt[r] = -1;
	for (int i = 1; i < n; i++) {
		int num1, num2;
		cin >> num1 >> num2;
		adj[num1].push_back(num2);
		adj[num2].push_back(num1);
	}
	dfs(r);

	for (int i = 0; i < q; i++) {
		int U;
		cin >> U;
		cout << subTree[U] << '\n';
	}


	return 0;
}