题解
dp的核心在于，增加一颗根节点时，以其为根节点的$ ans = max( \sum_{}^{}子节点不选 + r[new],max(\sum_{}^{}子节点选 , \sum_{}^{}子节点不选) ) $
code
#include<bits/stdc++.h>
using namespace std;
int vis[6005]={0};
vector<int> son[6005];
int dp[6005][2]={0};
int r[6005]={0};
void ss(int now)
{
dp[now][1]=r[now];
for(int i=0;i<son[now].size();i++)
{
int next=son[now][i];
ss(next);
dp[now][0]+=max(dp[next][0],dp[next][1]);
dp[now][1]+=dp[next][0];
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>r[i];
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
vis[x]=1;
son[y].push_back(x);
}
int i;
for(i=1;i<=n;i++)
if(!vis[i])
{
ss(i);
break;
}
cout<<max(dp[i][0],dp[i][1]);
return 0;
}