[1949] 우수 마을

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

1949번: 우수 마을

1의 조건을 만족시키면 3의 조건은 자연스레 만족하게 된다. 

현재 마을이 우수마을인경우, 그 하위 노드는 항상 우수마을이 아니도록 진행하고,

현재 마을이 우수마을이 아닌 경우, 2가지 모두로 분기한다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

int n, ans, dp[10001][2], a[10001];

vector<int> adj[10001];

bool vst[1000001];

void f(int cur) {

    dp[cur][1] = a[cur];

    for (auto& nxt : adj[cur]) {

        if (vst[nxt]) continue;

        vst[nxt] = true;

        f(nxt);

        dp[cur][1] += dp[nxt][0];

        dp[cur][0] += max(dp[nxt][0], dp[nxt][1]);

    }

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n;

    int i;

    for (i = 1; i <= n; i++) cin >> a[i];

    for (i = 0; i < n - 1; i++) {

        int A, B;

        cin >> A >> B;

        adj[A].push_back(B);

        adj[B].push_back(A);

    }

    vst[1] = true;

    f(1);

    ans = max(dp[1][0], dp[1][1]);

    cout << ans;

    return 0;

}

---