1. 题目

传送门=￣ω￣=

2. 题解

裸树型 dp
设 $f1[i]$表示选 i 时的最大收益，$f2[i]$表示不选 i 时的最大收益。
$f1[i]=\sum{f2[son[i]]} + v[i]$
$f2[i]=\sum{max(f1[son[i]],f2[son[i]])} + v[i]$

所以就没了

代码：

#include <bits/stdc++.h>
using namespace std;
int n,v[6005],root,f1[6005],f2[6005],dfs1(int),dfs2(int);
vector<int> g[6005];
bool book[6005];
int main()
{
    scanf("%d",&n),memset(f1,127,sizeof(f1)),memset(f2,127,sizeof(f2));
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1,a,b;i<n;i++)scanf("%d%d",&a,&b),g[b].push_back(a),book[a]=1;
    for(int i=1;i<=n;i++)if(!book[i]){root=i;break;}
    printf("%d\n",max(dfs1(root),dfs2(root)));
    return 0;
}
int dfs1(int u)
{
    if(f1[u]<1e8)return f1[u];f1[u]=v[u];
    for(int i=0;i<g[u].size();i++)f1[u]+=dfs2(g[u][i]);
    return f1[u];
}
int dfs2(int u)
{
    if(f2[u]<1e8)return f2[u];f2[u]=0;
    for(int i=0;i<g[u].size();i++)f2[u]+=max(dfs1(g[u][i]),dfs2(g[u][i]));
    return f2[u];
}