没有上司的舞会（树）

    // 状态表示f[u][0],f[u][1]:从以u为根的子数中选择的方案，包括不包括u点；属性：min
    // si表示u的子节点
    // 状态计算:f[u][0]=max(f[s1][0],f[s1][1])+max(f[s2][0],f[s2][1])+....
    //          f[u][1]=f[s1][0]+f[s2][0]+....

    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int N=5910;

    int n;
    int happy[N];
    int h[N],e[N],ne[N],idx;
    int f[N][2];
    bool has_father[N];

    void add(int a,int b)
    {
        e[idx]=b,ne[idx]=h[a],h[a]=idx ++;
    }

    void dfs(int u)
    {
        f[u][1]=happy[u];
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[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];
        memset(h,-1,sizeof h);

        //读入关系
        for(int i=0;i<n-1;i++)
        {
            int a,b;
            cin>>a>>b;
            has_father[a]=true;
            add(b,a);//将a接入b，以b为父节点
        }

        int root=1;
        //当有父节点时
        while(has_father[root])root++;

        dfs(root);

        cout<<max(f[root][0],f[root][1])<<endl;
        return 0;

    }