E17【模板】树形DP P1352 没有上司的舞会

#include<bits/stdc++.h>
using namespace std;
const int N=6100;
vector<int>G[N];
int f[N][2],w[N];
/*
    f[x][1]表示请x能得到的最大值 
    f[x][0]表示不请x能得到的最大值 
*/
void dp(int x)
{
    f[x][1]=w[x];f[x][0]=0;
	for(int y:G[x])
	{
		dp(y);
		f[x][1]+=f[y][0];
		f[x][0]+=max(f[y][1],f[y][0]);
    }
}
int main()
{
    int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    
    int rt=(n+1)*n/2;
    for(int i=1,x,y;i<=n-1;i++)
    {
        scanf("%d%d",&y,&x);
        G[x].emplace_back(y);
        rt=rt-y;
    }
 
	dp(rt);
    printf("%d\n",max(f[rt][1],f[rt][0]));
    return 0;
}