백준 15681 트리와 쿼리 - C++

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

15681번: 트리와 쿼리

문제 해석이 제일 오래 걸렸다..

 

트리의 정보가 입력으로 주어지고, 쿼리(정점의 번호)가 주어지면 해당 정점을 루트로 하는 서브 트리의 정점의 개수를 구하는 문제.

 

이게 가능한 모든 서브 트리를 경우를 모두 구해서 그 서브 트리들의 정점의 총합을 구하라는 문제인가? 생각했는데

입력으로 트리의 간선과 함께 트리 전체의 루트 역시 주어지고, 출력 예시를 보니 간단하게 자식 노드들을 모두 포함하는 경우, 즉 가장 큰 서브 트리 하나만 생각하면 되는거 같았다.

 

dfs 와 DP를 이용해서 풀었다. 사실 DP가 굳이..?

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <memory.h>


using namespace std;
using ll = long long;
ll dp[100010];
vector <ll> v[100010];

int n, r, q;

void dfs(ll x, ll par) {
	dp[x] = 1;
	for (ll next: v[x]) {
		if (next == par) continue;
		dfs(next, x);
		dp[x] += dp[next];
	}
}

int main(void) {

	scanf("%d %d %d", &n, &r, &q);

	int a, b;
	for (int i = 0; i < n -1; i++) {
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}

	dfs(r, 0);
	getchar();
	for (int i = 0; i < q; i++) {
		scanf("%d", &a);
		printf("%lld\n", dp[a]);
	}

	return 0;
}