头插法建立邻接表

具体逻辑见注释

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)


const int N = 6020;
int f[N][2];
bool iSon[N];

int e[N],ne[N],h[N],idx;
void add(int a, int b )  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}



void dfs(int root){

    for(int i=h[root];~i;i=ne[i]){
        int son=e[i];
        dfs(son);
        f[root][0]+=max(f[son][0],f[son][1]);
        f[root][1]+=f[son][0];//1表示选了当前的节点
    }

}


int main()
{
    int n;cin>>n;
    ffor(i,1,n+1) scanf("%d", &f[i][1]);


    memset(h, -1, sizeof h);
    ffor(i,0,n-1){
        int son,fa;
        scanf("%d%d", &son, &fa);
        iSon[son]=true;
        add(fa,son);
    }

    int root;
    ffor(i,1,n+1)
        if(!iSon[i]){
            root=i;
            break;
        }

    dfs(root);
    //输出选与不选中的较大的一个
    cout<<max(f[root][0],f[root][1])<<endl;

    return 0;
}