[BAE/<JOON> 문제풀이] 15681. 트리와 쿼리

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

15681번: 트리와 쿼리

핵심::

문제 힌트

 

풀이::

DP[정점 번호] = 자식 정점 개수

 

트리를 구성하고 탑다운 방식으로 정점 갯수를 센다.

 

사실 DP 배열에 저장할 필요도 없는게, 트리 구조라서 각 정점은 한번씩만 방문되기 때문에 메모이제이션 할 필요도 없다.

 

근데 왜 동적계획법 태그가 붙었는지 잘 모르겠다.

 

의견::

기본문제

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> dp;
vector<vector<int>> arr;
vector<vector<int>> t;

int re(int p) {
	int& ret = dp[p];
	if (ret != -1) return ret;
	ret = 1;
	for (const auto& nx : t[p]) {
		ret += re(nx);
	}
	return ret;
}

void maketree(int c, int p) {
	for (const auto& nx : arr[c]) {
		if (nx != p) {
			t[c].push_back(nx);			
			maketree(nx, c);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0); 
	int n, root, m;
	cin >> n >> root >> m;
	arr = vector<vector<int>>(n + 1);
	t = vector<vector<int>>(n + 1);
	dp = vector<int>(n + 1, -1);
	for (int i = 1; i <= n - 1; i++) {
		int s, d; cin >> s >> d;
		arr[s].push_back(d);
		arr[d].push_back(s);
	}
	maketree(root, -1);		
	re(root);
	for (int i = 1; i <= m; i++) {
		int q; cin >> q;
		cout << dp[q] << "\n";
	}
	return 0;
}