dp-우수마을

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

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;
}