ch_5401 没有上司的舞会

每个节点只与其子节点状态有关，所以设f[x][0/1]表示x点不选或选

建立一个虚点N+1链接到所有最高级的没有上司的上司，答案就是f[N+1][0]，因为虚点不可选

#include<iostream>
#include<cstdio>

#define ri register int
#define u int

namespace opt {

    inline u in() {
        u x(0),f(1);
        char s(getchar());
        while(s<'0'||s>'9') {
            if(s=='-') f=-1;
            s=getchar();
        }
        while(s>='0'&&s<='9') {
            x=(x<<1)+(x<<3)+s-'0';
            s=getchar();
        }
        return x*f;
    }

}

using opt::in;

#define NN 6005

namespace mainstay {

    u N,cnt,h[NN],v[NN],id[NN],f[NN][2];

    struct node{
        u to,next;
    }a[NN];

    inline void add(const u &x,const u &y){
        a[++cnt].to=y,a[cnt].next=h[x],h[x]=cnt;
    }

    void dfs(const u &x){
        f[x][1]=v[x];
        for(ri i(h[x]);i;i=a[i].next){
            u _y(a[i].to);
            dfs(_y);
            f[x][1]+=f[_y][0];
            f[x][0]+=std::max(f[_y][0],f[_y][1]);
        }
    }

    inline void solve(){
        N=in();
        for(ri i(1);i<=N;++i) v[i]=in();
        while(1){
            u _a(in()),_b(in());
            if(!_a&&!_b) break;
            add(_b,_a),++id[_a];
        }
        for(ri i(1);i<=N;++i) if(!id[i]) add(N+1,i);
        dfs(N+1);
        std::cout<<f[N+1][0];
    }

}

int main() {

    //freopen("x.txt","r",stdin);
    std::ios::sync_with_stdio(false);
    mainstay::solve();

}