(1949) 우수 마을

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

단계별로 풀어보기

36단계(트리에서의 동적 계획법) 2번째

 

 

 

편의상 1번 마을을 루트 노드로 가정한다.

dp[x]는 x번 마을을 루트 노드로 하는 서브트리에서 주민 수의 최대값이라고 하자.

dp[x][0]은 x번 마을이 우수 마을이 아닌 경우, dp[x][1]는 x번 마을이 우수 마을인 경우다.

DFS로 순회하면서 자식 마을을 먼저 탐색하고 DP를 갱신하면 된다.

1) x번 마을이 리프 노드라면 dp[x][0]=0, dp[x][1]=(x번 마을 인원수)이다.

2) x번 마을의 자식 노드 y번 마을에 대해 dp[x][0]은 y번 마을이 우수 마을이든 아니든 상관 없으므로 dp[y][0]과 dp[y][1] 중 큰 값을 더하고, dp[x][1]은 y번 마을이 우수 마을일 수 없으므로 dp[y][0]을 더한다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector adj(n+1, vector<int>()), dp(n+1, vector<int>(2));
  vector<int> v(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  
  for(int i=1;i<n;i++){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  
  auto dfs= [&](auto self, int now) -> void {
    dp[now][1]= v[now];
    
    for(int next:adj[now]){
      if(dp[next][1])  continue;
      
      self(self, next);
      dp[now][0]+= max(dp[next][0], dp[next][1]);
      dp[now][1]+= dp[next][0];
    }
  };
  
  dfs(dfs, 1);
  
  cout << max(dp[1][0], dp[1][1]);
  
  return 0;
}