年会-树形DP

解题思路:树形DP

    f[x][0]表示以x为根的子树,且x不参加舞会的最大快乐值

    f[x][1]表示以x为根的子树，且x参加了舞会的最大快乐值

    则f[x][0]=sigma{max(f[y][0],f[y][1])} (y是x的儿子)

    f[x][1]=sigma{f[y][0]}+h[x] (y是x的儿子)

    先找到唯一的树根root

    则ans=max(f[root][0],f[root][1])

注意事项:

参考代码:

#include <iostream>
#include <vector>
using namespace std;
const int N = 6005;
int h[N],v[N];
vector<int> son[N];
int f[N][2];
void dp(int x) {
	f[x][0]=0;
	f[x][1]=h[x];
	for(int i=0; i<son[x].size(); i++) {
		int y=son[x][i];
		dp(y);
		f[x][0]+=max(f[y][0],f[y][1]);
		f[x][1]+=f[y][0];
	}
}
int main() {
	int n;
	cin>>n;
	for(int i=1; i<=n; i++) cin>>h[i];
	for(int i=1; i<=n-1; i++) {
		int x,y;
		cin>>x>>y;
		son[y].push_back(x);
		v[x]=1;
	}
	int root;
	for(int i=1; i<=n; i++)
		if(!v[i]) {
			root=i;
			break;
		}
	dp(root);
	cout<<max(f[root][0],f[root][1])<<endl;
	return 0;
}