题解:本题主要考查树形DP。
简要题意:一个树,每个点有一个“快乐”值,父子结点不能同时快乐,问这个结构的最大快乐值。
1.树形DP:典型的树形DP,思考如何写出树规方程,即思考根与子节点的关系。
方程: f [ 1 ] [ p ] = m a x ( m a x ( f [ 1 ] [ p ] + f [ 0 ] [ i ] , f [ 1 ] [ p ] ) , f [ 0 ] [ i ] ) ; f[1][p]=max(max(f[1][p]+f[0][i],f[1][p]),f[0][i]); f[1][p]=max(max(f[1][p]+f[0][i],f[1][p]),f[0][i]);
//可以选自己,就是子节点不选时最大值+自己的值,或只是子节点不选时的最大值
f [ 0 ] [ p ] = m a x ( m a x ( f [ 0 ] [ p ] + f [ 1 ] [ i ] , f [ 1 ] [ i ] ) , m a x ( f [ 0 ] [ i ] , f [ 1 ] [ i ] ) ) ; f[0][p]=max(max(f[0][p]+f[1][i],f[1][i]),max(f[0][i],f[1][i])); f[0][p]=max(max(f[0][p]+f[1][i],f[1][i]),max(f[0][i],f[1][i]));
//可以不选自己,就是子节点选时+自己,或仅仅子节点选时最大
代码如下:
#include<iostream>
#include<algorithm>
using namespace std;
struct N
{
int start,to;
}t[99999];
int n,ans,a,b,root;
int h[99999],f[3][6666];
void dp(int p)
{
for(int i=t[p].to;i;i=t[i].start)
{
dp(i);
f[1][p]=max(max(f[1][p]+f[0][i],f[1][p]),f[0][i]);
f[0][p]=max(max(f[0][p]+f[1][i],f[1][i]),max(f[0][i],f[1][i]));
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>f[1][i];
for(int i=1;i<=n;i++)
{
cin>>a>>b;
h[a]++;
t[a].start=t[b].to;
t[b].to=a;
}
for(int i=1;i<=n;i++)
if(h[i]==0){root=i;break;}
dp(root);
ans=max(f[1][root],f[0][root]);
cout<<ans<<endl;
return 0;
}