思路：

本题属于树型DP(一般采用递归方式求解)

坑点

1.每次做题得先看看数据大小，本题数据范围广可能会爆int(经常考)，得用long存储
2.由于是树，是双向边得开两倍存储

递归写法一：

    private static int N=200010;//双向的所以得开两倍
    private static long[] f=new long[N];//表示包含根节点i的所有方案的集合，属性是最大值
    private static int idx,n;
    private static int[] e=new int[N],ne=new int[N],h=new int[N];
    private static int[] w=new int[N];
    public static void add(int a,int b) {
        e[idx]=b;ne[idx]=h[a];h[a]=idx++;//用邻接表存储
    }
    public static long dfs(int root,int father) {
        f[root]=w[root];//初始化，最坏情况下就是只有一个根节点不包含子节点
        for(int i=h[root];i!=-1;i=ne[i]) {
            int j=e[i];
            if(j==father)continue;//如果该节点曾经是root的父亲则不遍历
            //dfs(j, root);
            f[root]+=Math.max(dfs(j, root), 0);//大于0就加上去,数据可能会很大得用long存储
        }
        return f[root];
    }
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        Arrays.fill(h, -1);
        int n=scanner.nextInt();
        for(int i=1;i<=n;i++)//由于题目编号是从1开始的，下标得从1开始，后面添加操作是从一开始的
            w[i]=scanner.nextInt();
        for(int i=0;i<n-1;i++) {
            int a=scanner.nextInt();
            int b=scanner.nextInt();
            add(a, b);add(b, a);
        }

        dfs(1,-1);

        long res=Integer.MIN_VALUE;//有可能最大的结果为负值，所以初始化要负无穷
        for(int i=1;i<=n;i++) {
            res=Math.max(res, f[i]);//比较每个根节点的最大值
        }
        System.out.println(res);
    }

递归写法二：

    public static void dfs(int root,int father) {
        f[root]=w[root];
        for(int i=h[root];i!=-1;i=ne[i]) {
            int j=e[i];
            if(j==father)continue;
            dfs(j, root);
            f[root]+=Math.max(f[j], 0);//大于0就加上去,数据可能会很大得用long存储
        }
    }