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

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

15681번: 트리와 쿼리

1. 주의할 점

- DFS +DP를 이용하여 메모아이징을 사용해야 한다

 

2. 구현

- 모든 간선들의 정보를 V[] 배열에 담는다

- 입력 받은 Root를 기준으로 DFS()를 수행하며 메모아이징을 이용해서 해결한다. 또한, Visit[] 배열을 사용하여 해당 Node의 부모를 세지 않도록 한다

 

#include <iostream>
#include <vector>
using namespace std;
vector<int> v[100001];
bool visit[100001] = { false, };
int num[100001];
int node, query, s, e;

int dfs(int n) {
	if (num[n] != 0) return num[n];
	visit[n] = true;
	int ret = 1;
	for (int i = 0; i < v[n].size(); i++) {
		int next = v[n][i];
		if (visit[next]) continue;
		ret += dfs(next);
	}
	num[n] = ret;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int root;
	cin >> node >> root >> query;
	for (int i = 0; i < node - 1; i++) {
		cin >> s >> e;
		v[s].push_back(e);
		v[e].push_back(s);
	}
	num[root] = dfs(root);
	for (int i = 0; i < query; i++) {
		cin >> s;
		cout << num[s] << '\n';
	}
	return 0;
}