[백준] 1949 - 우수 마을

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

1949번: 우수 마을

 

다음과 같이 dp배열을 정의하면 거의 끝난다.

dp[i][j]는,

j가 0이면 해당 마을을 우수마을로 선정하지 않았을 때, 서브트리의 최대 우수 마을 주민 수 합

j가 1이면 해당 마을을 우수마을로 선정하였을 때, 서브트리의 최대 우수 마을 주민 수 합

 

그래서 일반 마을은 적어도 하나의 우수 마을과 인접해야 하므로 

하위 서브트리의 j가 0일때와 1일때를 각각 구해 조건에 맞게 답을 구하면 된다.

 

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

int n;
vector<vector<int>> v;
int num[10001], dp[10001][2];
int ans;

int dfs(int node, int pre, int g) {
	if (dp[node][g])return dp[node][g];

	int ret = 0;
	if (cnt)ret = num[node];

	for (auto& i : v[node]) {

		if (i != pre) {
			int no = dfs(i, node, 0);
			int yes = dfs(i, node, 1);
			if (g == 1) {
				ret += no;
			}
			else {
				ret += max(no, yes);
			}
		}
	}

	return dp[node][g] = ret;
}

int main() {

	cin >> n;
	v.resize(n + 1);
    
	for (int i = 1; i <= n; i++) {
		cin >> num[i];
	}

	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	cout << max(dfs(1, 0, 0), dfs(1, 0, 1));
}