문제

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다.

이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 '우수 마을'로 선정하려고 한다.

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, 주어진 조건을 만족하도록 '우수 마을'을 선정하는 프로그램을 작성하시오.

입력
첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.

출력
첫째 줄에 '우수 마을'의 주민 수의 총 합을 출력한다.

풀이

트리에서 DP로 풀어야 하는 문제이다.
한 마을에 대해서 이 마을이 우수마을인 경우와 그렇지 않은 경우를 나누어서 계산해야 한다.
루트노드가 일반 마을인 경우와 우수 마을인 경우 중
전체 우수마을의 인구가 더 많은 경우를 출력하기 위해 그 서브트리에 대해서 재귀적으로 같은 동작을 수행한다.
부모노드가 우수마을인 경우에 그 자식노드가 어떤 마을이 되는지, 부모노드가 일반 마을인 경우에 자식노드가 어떤 마을이 되는지 고민해야 한다.

문제의 2번 조건, 우수마을 끼리 인접할 수 없기 때문에 부모 작식간의
우수 마을-우수 마을 은 불가능하다.
따라서 부모가 우수마을이면 그 자식은 우수마을이 될 수 없다. 항상 일반 마을이여야 한다.

for (int child : graph[current])
	dp[current][true] += dp[child][false];

하지만 3번 조건에 의해서 일반 마을의 경우
우수마을-일반마을-일반마을-우수마을 은 가능하지만
일반마을-일반마을-일반마을은 불가능하다.
하지만 이러한 경우는 1번 조건에 의해서 발생하지 않게 된다.
우수마을로 선전된 마을 주민수의 최대 총합을 구해야 하기 때문에 우수마을이 될 수 있는 마을이 있다면 항상 우수마을로 선정되게 된다.

for (int child : graph[current])
	dp[current][false] += max(dp[child][false], dp[child][true]);

코드

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

int n;
vector<int> population;
vector<vector<int>> graph;
vector<vector<int>> dp;

void dfs_tree(int current, int parent){
    dp[current][true] = population[current];

    for (int child : graph[current]){
        if (child == parent) continue;
        
        dfs_tree(child, current);
        dp[current][false] += max(dp[child][false], dp[child][true]);
        dp[current][true] += dp[child][false];
    }
}

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

    cin >> n;
    graph.assign(n+1, vector<int>());
    population.assign(n+1, 0);
    dp.assign(n+1, vector<int>(2, 0));

    for (int i=1; i<n+1; i++){
        cin >> population[i];
    }

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

    dfs_tree(1, -1);

    cout << max(dp[1][0], dp[1][1]) << endl;

    return 0;
}