一道很经典的树形DP,设置一个点的有无,会影响子节点的有无。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=6e4+10;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N][2],h[N];
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
void treedp(int x,int fa)
{
    f[x][1]=h[x];f[x][0]=0;
    for(int k=last[x];k;k=a[k].next)
    {
        int y=a[k].y;if(y==fa)continue;treedp(y,x);
        f[x][1]+=f[y][0];f[x][0]+=max(f[y][0],f[y][1]);
    }
}
bool v[N];
int main()
{
    int n,root;qr(n);
    for(int i=1;i<=n;i++)qr(h[i]);
    for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(y,x),v[x]=1;
    for(int i=1;i<=n;i++)if(!v[i])root=i;
    treedp(root,0);
    qw(max(f[root][0],f[root][1]));puts("");
    return 0;
}