https://www.acmicpc.net/problem/1949
문제 유형은 트리 dp에 속한다.
문제 조건은 다음과 같은데,
1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.
매우 흥미롭게도 3번 조건은 필요가 없다. 왜냐하면, 1번에서 주민의 수의 총 합을 최대로 하는 과정에서 3번 조건이 알아서 충족이 되기 때문이라고 한다. 완벽하게 이해가 되지는 않지만 그렇다고 한다.
코드 :
#include <iostream>
#include <vector>
#include <cstring>
//우수마을
using namespace std;
int N;
int dp[10010][2];
int A[10010];
vector<int> v[10010];
int dfs(int x,int k,int par){
if(dp[x][k]!=-1) return dp[x][k];
if(k==1)dp[x][1]=A[x];
else dp[x][0]=0;
for(int i:v[x]){
if(i==par) continue;
if(k==1) dp[x][1]+=dfs(i,0,x);
else dp[x][0]+=max(dfs(i,0,x),dfs(i,1,x));
}
// cout<<x<<" "<<k<<" "<<dp[x][k]<<'\n';
return dp[x][k];
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i=1;i<=N;i++) cin>>A[i];
for(int i=1,u,x;i<N;i++){
cin>>u>>x;
v[u].push_back(x);
v[x].push_back(u);
}
memset(dp,-1,sizeof(dp));
v[0].push_back(1);
dfs(0,0,0);
cout<<max(dp[0][0],dp[0][1]);
return 0;
}