[트리 DP(Top-Down)] 백준 1949 우수 마을 C++

 

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

1949번: 우수 마을

 

#include<iostream>
#include<vector>
#define MAX 10005
using namespace std;

int num, a, b, ans;
int dp[MAX][2];
int visited[MAX];
int people[MAX];
vector<int> tree[MAX];  // 배열, 리스트

void calSubTree(int n) { // n이 루트인 subtree dp 계산
    for (int j = 0; j < tree[n].size(); j++) {
        int temp = tree[n][j];
        if (visited[temp]) continue;
        visited[temp] = 1;
        calSubTree(temp);

        dp[n][0] += dp[temp][1];
        dp[n][1] += max(dp[temp][0], dp[temp][1]);
    }
    dp[n][0] += people[n];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> num;
    
    for (int i = 0; i < num; i++) cin >> people[i];

    for (int i = 0; i < num-1; i++) {
        cin >> a >> b;
        a -= 1;
        b -= 1;
        tree[a].push_back(b);  // if(a<b) 나누지 말고 visited 사용
        tree[b].push_back(a);
    }
    
    visited[0] = 1;
    calSubTree(0);
    ans = max(dp[0][0], dp[0][1]);
    cout << ans;
}