算法分析

树形dp

状态表示

• f[u][0]：所有以u为根的子树中选择，并且不选u这个点的方案

• f[u][1]：所有以u为根的子树中选择，并且选u这个点的方案

• 属性：Max

状态计算

当前u结点不选，子结点可选可不选

• $f[u][0] = \sum max(f[s_i,0],f[s_i,1])$

当前u结点选，子结点一定不能选

• $f[u][1] = \sum (f[s_i,0])$

时间复杂度 $O(n)$

Java 代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main{
    static int N = 6010;
    static int[] happy = new int[N];
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int idx = 0;
    static int[][] f = new int[N][2];
    static boolean[] has_fa = new boolean[N];
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    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][1], f[j][0]);
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 1;i <= n;i ++) happy[i] = scan.nextInt();
        Arrays.fill(h, -1);
        for(int i = 0;i < n - 1;i ++)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            add(b,a);
            has_fa[a] = true;
        }
        int root = 1;
        while(has_fa[root]) root ++;
        dfs(root);

        System.out.println(Math.max(f[root][0], f[root][1]));
    }
}