[BOJ 1949] 우수 마을

문제

www.acmicpc.net/problem/1949

1949번: 우수 마을

 

---

풀이

트리DP를 사용합니다.

트리가 주어졌을 때, 배열 \(dp\)를 다음 두 가지 경우로 생각해 정의할 수 있습니다:

 

• \(dp[i][0]:\) \(i\)가 우수 마을이 아닐 경우의 마을 주민 수 합의 최대값.
• \(dp[i][1]:\) \(i\)가 우수 마을일 경우의 마을 주민 수 합의 최대값.

\(i\)의 자식 노드들을 \(c_{1}, c_{2}, c_{3}, ... , c_{m}\)이라고 할 때,

\(i\)가 우수 마을이 아닐 경우에는 적어도 인접한 하나의 마을이 우수 마을이어야 하므로, \(c_{j}\)의 마을이 우수 마을도 일반 마을도 될 수 있습니다.

\(i\)가 우수 마을일 경우에는 인접한 마을이 우수 마을이 되면 안되므로, \(c_{j}\)의 마을은 일반 마을만 될 수 있습니다.

그러므로, \(dp[i][0]\)과 \(dp[i][1]\)에 다음 값을 저장합니다:

$$dp[i][0] = \sum_{j = 1}^{m} \max\begin{cases}
dp[c_{j}][0]\\ 
dp[c_{j}][1]
\end{cases}$$

$$dp[i][1] = v_{i} + \sum_{j = 1}^{m} dp[c_{j}][0]$$

여기서 \(v_{i}\)은 \(i\)번 마을의 주민 수를 나타냅니다.

 

\(\max\begin{cases}
dp[1][0]\\
dp[1][1]
\end{cases}\)이 답이 됩니다.

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int N;
vector<vector<int>> dp;
vector<vector<int>> node;

void solve(int cur, int pnode) {
    for (auto next : node[cur]) {
        if (next != pnode) {
            solve(next, cur);
            dp[cur][0] += max(dp[next][0], dp[next][1]);
            dp[cur][1] += dp[next][0];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    dp.resize(N + 1, vector<int>(2, 0));
    node.resize(N + 1);
    for (int i = 1; i <= N; ++i) cin >> dp[i][1];

    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        node[a].push_back(b);
        node[b].push_back(a);
    }

    solve(1, 0);

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

    return 0;
}