Tree DP

백준 1949번 우수 마을 문제풀이

[1949 우수 마을] https://www.acmicpc.net/problem/1949 .
트리에서 dp를 수행한다.

문제상황 파악하기.

1. 정점의 합이 최대여야한다.
2. 고르는 정점들이 인접하면 안된다.
3. 안 고른 정점 옆에는 최소한 한 개는 고른 정점이 있어야한다.
   이것도 3번이 낚시인데 사실 그리디 하게 생각해보면 무조건 고르는게 이득이다.
   왜냐면 주민 수는 항상 양수 이기 때문이다.

Tree에서 DP를 어떻게 하는가?

그래프 탐색을 하면서 dp를 쌓아 올리는 것이다.
dfs로 깊게 들어간다음 leaf에서 dp값을 초기화하고 올라오면서 그 dp값을 이용하여 계산한다.

아이디어 얻기.

가장 깊게 들어가면 leaf는 0or 1이다. 이말은 이것을 포함 안하냐 하냐의 문제이다.
따라서 dp[k][bool] bool이 0이면 k를 안골랐을 때, bool이 1이면 k를 골랐을 때 우수마을의 최대 주민 수 이다.

주의할 점

3번 조건이 낚시인 점?

실제 코드

나머지 주의 할 점은 코드에 주석으로 처리했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define fast_io cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;

int n, V[10001];
vector<int> adj[10001];
int dp[10001][2];   //N번 정점이 우수마을 일때/아닐때 최대 주민수
bool visited[10001];

void dfs(int here, int parent){
    visited[here] = true;
    dp[here][0] = 0;
    dp[here][1] = V[here];

    for(int next : adj[here]){
        if(next==parent) continue;
        if(!visited[next]) dfs(next, here);

        dp[here][0] += max(dp[next][1], dp[next][0]);
        dp[here][1] += dp[next][0];
    }
}

int main(){
    fast_io;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> V[i];
    for(int i=1;i<n;i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]);
}