(2213) 트리의 독립집합

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

단계별로 풀어보기

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

 

 

 

똑같은 DP지만 역추적까지 해야 하는 문제.

부모 노드가 선택되지 않았으면서(아래 코드의 flag 함수로 관리) dp[x][1](선택되었을 때)이 dp[x][0](선택되지 않았을 때)보다 크다면 x번 노드는 최대값을 만드는 정점이다. DFS를 한 번 더 돌리며 선택된 정점을 전부 찾으면 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
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), ans;
  
  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];
    }
  };
  
  auto track= [&](auto self, int now, bool flag) -> void {
    if(flag && dp[now][1]>dp[now][0]){
      ans.push_back(now);
      flag= false;
    }else{
      flag= true;
    }
    
    dp[now][1]= 0;
    
    for(int next:adj[now]){
      if(dp[next][1]==0)  continue;
      
      self(self, next, flag);
    }
  };
  
  dfs(dfs, 1);
  
  if(dp[1][1]>dp[1][0]){
    cout << dp[1][1] << "\n";
    track(track, 1, true);
  }else{
    cout << dp[1][0] << "\n";
    track(track, 1, false);
  }
  
  sort(ans.begin(), ans.end());
  
  for(int elem:ans)  cout << elem << " ";
  
  return 0;
}