NC51178 没有上司的舞会

状态表示：
父亲和儿子不能同时选，父节点(u)选或不选会影响子树的结果。
(f(u,0))表示不选(u)时，以(u)为根的子树快乐质数总和的最大值。此时，(u)的子节点可以参加，也可以不参加；
(f(u,1))表示选(u)时，以(u)为根的子树快乐质数总和的最大值。此时，(u)的所有子节点都不能参加。

状态转移：

[f(u,0)=sum_{j in Son(u)}max(f(j,0),f(j,1)) \ f(u,1)=Happy[u]+sum_{j in Son(u)}f(j,0) ]

其中，(Son(u))表示(u)的子节点集合。

边界：
(f[leaf_i][0]=0，f[leaf_i][1]=Happy[leaf_i])。

const int N=6010;
vector<int> g[N];
int f[N][2];
int happy[N];
int fa[N];
int n;

void dfs(int u)
{
    f[u][0]=0;
    f[u][1]=happy[u];
    
    for(int i=0;i<g[u].size();i++)
    {
        int j=g[u][i];
        dfs(j);
        f[u][0]+=max(f[j][0],f[j][1]);
        f[u][1]+=f[j][0];
    }
}

int main()
{
    cin>>n;
    
    for(int i=1;i<=n;i++) cin>>happy[i];

    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        g[b].pb(a);
        fa[a]=b;
    }

    int root=1;
    while(fa[root]) root=fa[root];
    
    dfs(root);

    cout<<max(f[root][0],f[root][1])<<endl;
    //system("pause");
    return 0;
}