[백준] 15681-트리와 쿼리(C++)

문제링크: https://www.acmicpc.net/problem/15681

15681번: 트리와 쿼리

 

서브트리들의 정점 갯수를 구하는 문제

 

부모 노드의 경우 탐색을 해주면 안되는데,

이러한 문제를 메모이제이션을 통해서 문제를 해결할 수 있습니다.

 

아래는 정답 코드입니다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

vector <int> vec[100001];
int n, r, q;
int dp[100001];

int dfs(int n) {
	if (dp[n] != -1)
		return dp[n];
	
	int& ret = dp[n];	
	ret = 1;
	for (int i = 0; i < vec[n].size(); i++) {
		int next = vec[n][i];
		if (dp[next]!= -1)
			continue;
		ret += dfs(next);
	}
	
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> r >> q;
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
		dp[i] = -1;
	dp[r] = dfs(r);
	for (int i = 0; i < q; i++) {
		int c;
		cin >> c;
		cout << dp[c] << "\n";
	}


	return 0;
}