백준 15681번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	골드 5

---

풀이

 트리를 배웠다면 아주 간단한 문제이다. 쿼리로 들어오는 정점을 루트로 가지는 서브트리의 정점의 개수를 구하는 문제이다. 풀이방법은 간단하다. 입력으로 들어온 루트노드로부터, 자식 노드로 dfs하며, 정점의 개수를 저장하고 세어준다. 이때, 모든 정점은 적어도 자기 자신을 트리로 가지고 있기 때문에, 서브트리의 정점 개수를 저장할 배열을 1로 초기화한 후, 각 서브트리로 재귀하며 개수를 세어준다.

코드

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int n, r, q;
vector<vector<int>> tree;
vector<int> query, child;

void input() {
	int a, b;

	cin >> n >> r >> q;
	tree.resize(n + 1), query.resize(q), child.resize(n + 1, 1);

	for(int i = 1; i < n; i++) {
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int& q : query) cin >> q;
}

int dfs(int parent, int cur) {
	for(int& c : tree[cur]) {
		if (c == parent) continue;
		child[cur] += dfs(cur, c);
	}
	return child[cur];
}

void sol() {
	dfs(-1, r);
	for(int& q : query) cout << child[q] << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol();
}