HDU1520.Anniversary party(树形DP&DFS）

题目传送门

思路：状态转移方程有两个：1.不选父结点，则加上子结点选或者不选的最大值，2.选父结点，则加上不选子结点的最大值。具体看代码。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=6e3+5;
int dp[N][2],n,w[N],fa[N],a,b;
vector<int>e[N];
void dfs(int u){
	dp[u][0]=0,dp[u][1]=w[u];
	for(auto v:e[u]){
		dfs(v);
		dp[u][0]+=max(dp[v][0],dp[v][1]);//不选父结点 
		dp[u][1]+=dp[v][0];//选父结点. 
	}
}
int main(){
	while(~scanf("%d",&n)){
	for(int i=1;i<=n;i++) scanf("%d",&w[i]),e[i].clear(),fa[i]=0;//初始化 
	while(scanf("%d%d",&a,&b)){
		if(!a&&!b) break;
		e[b].push_back(a);//有向边 
		fa[a]=b;
	}
	int rt=1;
	while(fa[rt]) rt=fa[rt];//找根. 
	dfs(rt);
	printf("%d\n",max(dp[rt][0],dp[rt][1]));
	} 
	return 0;
}