우수 마을 / Tree DP

www.acmicpc.net/problem/1949

1949번: 우수 마을

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


using namespace std;

int n;
int towns[10001];
vector<vector<int>>v(10001);

int dp[10001][2];
bool visited[10001];

void dfs(int idx) {

	visited[idx] = true;

	dp[idx][0] = 0;
	dp[idx][1] = towns[idx];
	
	for (int i = 0; i < v[idx].size(); i++) {
	
		if (visited[v[idx][i]] == true) { continue; }
		
		dfs(v[idx][i]);   
		
		
		dp[idx][0] += max(dp[v[idx][i]][1], dp[v[idx][i]][0]); //현재마을이 우수마을이 아니라면 다음마을은 우수 마을일수도 아닐 수도 있음.
		dp[idx][1] += dp[v[idx][i]][0]; //현재마을이 우수마을이라면 다음 마을은 무조건 우수마을이아님

		


		
	}
	

	


}



int main() {
	

	cin >> n;


	for (int i = 0; i < n; i++) {
	
		cin >> towns[i];
	}

	int a,b;

	for (int i = 0; i < n - 1; i++) {
	
		cin >> a;
		cin >> b;

		v[a].push_back(b);
		v[b].push_back(a);

	}

	dfs(1);


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


}