2342 Anniversary party

問題概要

N人の人がいて、それぞれの人の宴会能力が与えられる。
また、i番目の人がj番目の人の直属の上司であるという関係をグラフにすると
木構造になるものとする。

今、パーティを開きたいが、ある人と、その直属の上司が同時にパーティに参加しているという状態は避けたい。
このような制約のもと、パーティに参加している人の宴会能力の和の最大値を求めよ。

N≦6000、宴会能力は-128以上127以下とする。

解法

dp[i]をi番目の人がパーティに出席しない場合の、i番目の人以下の木の宴会能力の和の最大値、
dp2[i]をi番目の人以下の木の宴会能力の和の最大値とする。

するとdp[i]は(iが出席せずに、iの子のdp2を足した値)と(iが出席してdp[iの子]を足した値)の大きいほうという漸化式が立つのでDPできる。

ソースコード

int n,dp[6000],dp2[6000],p[6000];
bool rt[6000];
vector<vector<int> > e;

void rec(int c){
	int s=p[c];
	fr(i,e[c]){
		rec(*i);
		dp[c]+=dp2[*i];
		s+=dp[*i];
	}
	dp2[c]=max(s,dp[c]);
}
int main(){
	while(scanf("%d",&n),n){
		e.clear(); e.resize(n);
		rep(i,n){
			scanf("%d",p+i); dp2[i]=p[i];
			dp[i]=0; rt[i]=1;
		}
		rep(i,n-1){
			int a,b; scanf("%d%d",&a,&b); a--; b--;
			e[b].pb(a); rt[a]=0;
		}
		int r=0; for(;r<n;r++)if(rt[r])break;
		rec(r);
		printf("%d\n",dp2[r]);
	}
	return 0;
}