算法分析

树形dp

状态表示

• $f[u]$:在以u为根的子树中包含u的所有连通块的权值的最大值

状态计算

假设s1，s2,…sk 是u的孩子

• $f[u] = w[u] + max(f[s1],0) + max(f[s2],0) + … max(f[sk],0)$

从根结点开始深度优先遍历每个子结点

时间复杂度 $O(n)$

参考文献

蓝桥杯辅导课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 100010, M = N * 2;
    static int n;
    static int[] w = new int[N];
    static long[] f = new long[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static void dfs(int u,int father)
    {
        f[u] = w[u];

        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            dfs(j,u);
            f[u] += Math.max(f[j],0);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());

        String[] s1 = br.readLine().split(" ");
        for(int i = 1;i <= n;i ++) w[i] = Integer.parseInt(s1[i - 1]);
        Arrays.fill(h, -1);
        for(int i = 0;i < n - 1;i ++)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            add(a,b);
            add(b,a);
        }
        dfs(1,-1);
        long res = f[1];
        for(int i = 2;i <= n;i ++) res = Math.max(res, f[i]);
        System.out.println(res);
    }
}