[C/C++] 백준 1949번 - 우수 마을 (트리 dp)

 

<코드>

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

int N, a, b;
int citizen[10001];
int dp[10001][2];
bool visit[10001];
vector<int> v[10001];

void DFS(int now) // 현재, 합계, 우수마을여부
{
	visit[now] = true;

	dp[now][0] = 0;
	dp[now][1] = citizen[now];

	for (int next : v[now])
	{
		if (!visit[next])
		{
			DFS(next);

			// 현재마을 != 우수마을 이라면 다음마을은 우수마을이거나 우수마을이 아님
			dp[now][0] += max(dp[next][0], dp[next][1]);

			// 현재마을 == 우수마을 이라면 다음마을은 우수마을이 아님
			dp[now][1] += dp[next][0];
		}
	}
}

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

	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> citizen[i];

	for (int i = 1; i < N; i++)
	{
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	DFS(1);

	cout << max(dp[1][0], dp[1][1]);

}

 

 

 

www.acmicpc.net/problem/1949

1949번: 우수 마을