5、树形DP

AcWing 285. 没有上司的舞会

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }
    int N = 6010;
    int n;
    int happy[]=new int[N]; //每个职工的高兴度
    int f[][]=new int[N][2]; //上面有解释哦~
    int e[]=new int[N],ne[]=new int[N],h[]=new int[N],idx; //链表，用来模拟建一个树
    boolean has_father[]=new boolean[N]; //判断当前节点是否有父节点

    void insert(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);
            //不选u的话
            f[u][0]+= Math.max(f[j][0],f[j][1]);
            //选了u的话，就得从孩子结点且不选中找
            f[u][1]+= f[j][0];
        }
    }
    //f[u][0]：表示所有以u为根节点的子树选择，且不选u的集合
    //f[u][1]：表示所有以u为根节点的子树选择，且选u的集合
    //属性：Max
    void init() {
        Scanner sc = new Scanner(System.in);
        n=sc.nextInt();
        Arrays.fill(h,-1);
        for (int i = 1; i <= n; i++) {
            happy[i]=sc.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            has_father[a]=true;
            insert(b,a);
        }
        int root = 1; //用来找根节点
        while(has_father[root]) root ++; //找根节点
        dfs(root);
        System.out.println(Math.max(f[root][0],f[root][1]));
    }
}