算法分析

状态表示

$f[i, 0]$：在点 $i$ 不摆放警卫，且被父结点看到的所有摆放方案的最小花费

$f[i, 1]$：在点 $i$ 不摆放警卫，且被子结点看到的所有摆放方案的最小花费

$f[i, 2]$：在点 $i$ 摆放警卫的所有方案的最小花费

状态转移

$f[i, 0] = \sum min (f[j, 1] , f[j, 2])$

$f[i, 2] = \sum min (f[j, 0] , f[j, 1] , f[j, 2])$

$f[i, 1] = min ({f[k, 2] + \sum_{j \ne k}min({f[j, 1] , f[j, 2]})})$

注意：

计算$f[i, 1]$时，先把所有儿子的$min({f[j, 1] , f[j, 2]})$的总和 $sum$ 计算出来，当使用第 $k$ 个儿子放警卫时，把第 $k$ 个儿子的 $ min({f[k, 1] , f[k, 2]}) $ 减去，便得到了 $\sum_{j \ne k}min({f[j, 1] , f[j, 2]})$

时间复杂度 $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 = 1510;
    static int[][] f = new int[N][3];
    static int[] w = new int[N];
    static boolean[] has_fa = new boolean[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 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][2] = w[u];
        int sum = 0;
        for(int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];

            dfs(j);

            f[u][0] += Math.min(f[j][1], f[j][2]);
            f[u][2] += Math.min(f[j][0], Math.min(f[j][1], f[j][2]));
            sum += Math.min(f[j][1], f[j][2]);
        }

        f[u][1] = 0x3f3f3f3f;

        for(int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];

            f[u][1] = Math.min(f[u][1], f[j][2] + sum - Math.min(f[j][1], f[j][2]));
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());
        Arrays.fill(h, -1);
        for(int i = 0;i < n;i ++)
        {
            String[] s1 = br.readLine().split(" ");
            int a = Integer.parseInt(s1[0]);
            w[a] = Integer.parseInt(s1[1]);
            int cnt = Integer.parseInt(s1[2]);
            for(int j = 3;j < s1.length;j ++)
            {
                int b = Integer.parseInt(s1[j]);
                add(a, b);
                has_fa[b] = true;
            }
        }
        int root = 1;
        while(has_fa[root]) root ++;
        dfs(root);

        System.out.println(Math.min(f[root][1], f[root][2]));
    }
}