$$\color{Red}{皇宫看守-极小边覆盖-树形DP}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。

皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中结点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。

已知，在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。

大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。

帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。

输入格式

输入中数据描述一棵树，描述如下：

第一行 n，表示树中结点的数目。

第二行至第 n+1 行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号 i，在该宫殿安置侍卫所需的经费 k，该结点的子结点数 m，接下来 m 个数，分别是这个结点的 m 个子结点的标号 r1,r2,…,rm。

对于一个 n 个结点的树，结点标号在 1 到 n 之间，且标号不重复。

输出格式

输出一个整数，表示最少的经费。

数据范围

0 < n ≤ 1500

输入样例：

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

输出样例：

25

样例解释：
在2、3、4结点安排护卫，可以观察到全部宫殿，所需经费最少，为 16 + 5 + 4 = 25。

树形DP：dfs结合dp: 这道题是带权的极小边覆盖

我的没有上司的舞会题解 类似的一道题目，也是状态机相关的树形dp

我的战略游戏题解 类似的一道题，这道题是极小点覆盖

1.算法细节

• 不难看出，此题和树的重心 类似，只是存值使用了两个维度的状态表达式，但是为什么树的重心我们采用了st的bool数组，代表一个点是否可以遍历到，本题却不用了呢？

非常简单，树的重心是无向图，我们在求一颗确定根节点的树的结点数量，利用了这些边去遍历结点，我们使用st的bool数组是为了防止遍历过程中走到根节点之上，陷入死循环。
本题是有向图，故不会出现遍历到根节点的可能。

• 如何设计状态表达式和状态方程？为什么计算各不相同？

本题的节点关系以一颗树的图来保存，一个位置i的状态j用状态0和1和2表示。而我们是使用dfs进行遍历树的节点，故我们要进行的转移是枚举节点的子节点和它本身的状态关系。

极小边覆盖是指在一个图中，选取最少的边，使得所有的顶点都至少与其中一条边相连。

状态方程细节
f[i][j]:代表着i节点位置,状态为j

1. 0 -> 当前节点位置不放，而边被父节点放置的士兵覆盖

2. 1 -> 当前节点位置不放，而边被子节点放置的士兵覆盖

3. 2 -> 当前节点位置放，而边被自己放置的士兵覆盖

状态转移：

极小边覆盖的含义是极小的边数覆盖所有的点

0状态，因为当前节点不放，父节点放，当前节点和父节点会被父节点的士兵存在而连的边覆盖。那么当前节点已经被覆盖了，子节点可以存在士兵，去连和它的子节点的边，覆盖它子节点，即为子节点的状态2。也可以不放士兵，但是已经默认父节点不放了，只能为子节点的状态1，即被自己的子节点覆盖的状态转移而来。
故此时状态方程转移为：
f[father][0] = min(f[son][1], f[son][2]) (每个子节点均为如此情况，故需要累加)

1状态，因为当前节点不放，子节点放，当前节点和子节点会被子节点的士兵存在而连的边覆盖。那么当前节点已经被覆盖了，它只能转移到父节点存在士兵的情况。当前状态来自于：去连和它的子节点的边，覆盖当前节点，即为子节点的状态2，但是它有无数个子节点，只需要一个子节点有士兵，当前节点就会被覆盖，所以我们需要枚举最合适的子节点放士兵的情况（消耗最小），而其他的子节点可以为状态1或状态2（不能为0，因为当前节点固定不放，子节点无法被父节点存在士兵而连的边覆盖），这里其他的子节点就从状态1和2取消耗最少的情况。

这里每次遍历切换子节点，需要分别计算当前子节点放置，状态2，其他子节点状态1或2的最小值，需要开辟两个变量存储，然后进行迭代更新，太麻烦了。
但是很巧妙的是，我们的f[father][0]计算了所有子节点状态1或2的最小值的求和。我们只需要一次dfs结束后，重新再dfs遍历子节点，用这个遍历，枚举到一个子节点，更新f[father][1]的值：当前子节点为状态2，而其他子节点状态1或2最小值的求和转换为，f[father][0]减去当前节点状态1或2的最小值即可。

故此时状态方程转移为：
f[father][1] = min(f[father][1], f[son][2] + f[father][0] - min(f[son][1], f[son][2])) (每个子节点均为如此情况，但:是更新不是累加)

这里是状态机的思想，但是节点位置之间的关系使用的是树来存储和线性不同

2状态，因为当前节点放置士兵，当前节点和父节点会被当前节点的士兵存在而连的边覆盖。那么当前节点可以覆盖父节点和所有的子节点，那么它所有的相邻节点，不管是父节点还是子节点，均可以为0, 1, 2的状态。故我们dfs更新值，子节点应该从三个状态最小值的状态转移而来，因为可以存在多个子节点，所以需要累加所有子节点的值，同时因为这个点放置了士兵，还要加上当前节点放士兵的消耗，我们就放在初始化之初，就先给f[father][2]赋值为w[father]。

这里就引入数值的初始化，我们dfs之初可以完成枚举当前节点的初始化

f[father][0] = 0; // 累加子节点状态 故初始化为0
f[father][1] = (int) 1e9; // 求最小值所以优先初始化无穷
f[father][2] = w[father]; // 求自己放置的代价 故需要加自己

故此时状态方程转移为：
f[father][2] = min(f[son][0], f[son][1], f[son][2]) (每个子节点均为如此情况，故需要累加)

2.具体代码

java

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

public class Main {
    static int N = 1510, n, idx;
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int[] w = new int[N];

    static boolean[] st = new boolean[N];
    static int[][] f = new int[N][N];

    static void add(int x, int y) {
        e[idx] = y;
        ne[idx] = h[x];
        h[x] = idx++;
    }

    static void dfs(int father) {
        f[father][0] = 0; // 累加子节点状态 故初始化为0
        f[father][1] = (int) 1e9; // 求最小值所以优先初始化无穷
        f[father][2] = w[father]; // 求自己放置的代价 故需要加自己

        for (int i = h[father]; i != -1; i = ne[i]) {
            int son = e[i];
            dfs(son);
            f[father][0] += Math.min(f[son][1], f[son][2]);
            f[father][2] += Math.min(Math.min(f[son][0], f[son][1]), f[son][2]);
        }
        for (int i = h[father]; i != -1; i = ne[i]) {
            int son = e[i];
            // 上面的递归已经把f[father][0] f[father][2]算出来了
            // 而f[father][0] 记录了所有子节点自己被自己观察，或者被子节点的子节点观察的总和
            // 而求f[father][1] 要求我们找寻最优选取的，且能观察到父节点的子节点
            // 我们遍历子节点的过程中，直接利用f[father][0] 减去当前枚举节点 min(f[son][1], f[son][2])即可
            f[father][1] = Math.min(f[father][1],f[son][2] + f[father][0] - Math.min(f[son][1], f[son][2]));
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            int father = Integer.parseInt(s[0]);
            w[father] = Integer.parseInt(s[1]);
            int sonCount = Integer.parseInt(s[2]);
            for (int j = 0; j < sonCount; j++) {
                int son = Integer.parseInt(s[3 + j]);
                add(father, son);
                st[son] = true;
            }
        }
        int root = 1;
        while (st[root]) root++;
        dfs(root);
        System.out.println(Math.min(f[root][1], f[root][2]));
    }
}