BOJ 1949 우수 마을

1 개요

BOJ 1949 우수 마을

• 백준 온라인 저지 1949번 문제
• BOJ 38단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> cnt;
vector<int> node[10001];
bool visited[10001] = {};
int dp[2][10001] = {};

void dfs(int cur) {
	if (visited[cur]) return;
	visited[cur] = true;
	dp[0][cur] = 0;
	dp[1][cur] = cnt[cur];
	for (int next : node[cur]) {
		if (visited[next]) continue;
		dfs(next);
		dp[0][cur] += max(dp[0][next], dp[1][next]);
		dp[1][cur] += dp[0][next];
	}
}

void solve() {
	dfs(1);
	cout << (max(dp[0][1], dp[1][1]));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	cnt.push_back(0);
	int a, b;
	for (int i=0; i<N; i++) {
		cin >> a;
		cnt.push_back(a);
	}
	for (int i=0; i<N; i++) {
		cin >> a >> b;
		node[a].push_back(b);
		node[b].push_back(a);
	}
	solve();
}