java 代码

import java.util.*;
public class Main{
    //邻接表
    static int[] ne,h,e,happy;
    static int[][] f;
    static boolean[] has_fa;
    static int idx;
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        ne=new int[n+1];;
        happy=new int[n+1];
        has_fa=new boolean[n+1];
        f=new int[n+1][2];//树形dp相当于优化dfs 所以初值不用管，递归到最内层会赋值的。
        h=new int[n+1];
        e=new int[n+1];
        Arrays.fill(h,-1);//初始化邻接表 
        //读入happy
        for(int i=1;i<=n;i++) happy[i]=sc.nextInt();
        //读入邻接表
        for(int i=1;i<=n-1;i++){
            int a=sc.nextInt();
            int b=sc.nextInt();
            add(b,a);//b是父亲 把a加到b后面
            has_fa[a]=true;;
        }
        //找到根节点 has_fa中为false的点。
        int root=1;
        while(has_fa[root]) root++;
        //计算root的两个状态
        dfs(root);
        System.out.println(Math.max(f[root][0],f[root][1]));
    }
    public static 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][1]+=f[j][0];
            f[u][0]+=Math.max(f[j][0],f[j][1]);
        }
    }
    public static void add(int a,int b){
        //把b加到a后面
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
}