우수 마을 / Tree DP

연구하는개발자 2021. 4. 24. 02:00

728x90

www.acmicpc.net/problem/1949

1949번: 우수 마을

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며,

www.acmicpc.net

#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]);


}