$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题类似于 AcWing 323. 战略游戏 ，但不完全一样

战略游戏是每一条边至少选择一个端点，这道题的对象是点，即点 $u$ 及其所有与之相邻的点中，至少选择一个点

这道题也可以用状态机来考虑，对于点 $u$ 而言，我们先设定两种状态：选择该端点与不选择该端点

可以发现，如果不选择点 $u$ ，说明与点 $u$ 相邻的所有点中必然有一个点是被选择的（设为 $x$ ），那么 $x$ 可以是 $u$ 的子节点，也可以是 $u$ 的父节点，这就说明我们还需要细分

我们定义 $f[u][k]$ 表示：考虑以 $u$ 为根的子树，处于状态 $k$ 下的所有选择，属性为花费的最小值

• 当 $k=0$ 时，表示点 $u$ 的父节点被选择

• 当 $k=1$ 时，表示点 $u$ 的子节点被选择

• 当 $k=2$ 时，表示点 $u$ 自己被选择

下面我们分类讨论这三种情况：

当 $k=0$ 时，说明 $u$ 的父节点被选择，$u$ 不需要选择，因此 $u$ 的子节点没有限制，可选可不选

• $u$ 的子节点不选的情况：$f[son_i][1]$ ，子节点不选，说明子节点的子节点被选择
• $u$ 的子节点选择的情况：$f[son_i][2]$

对于每个子节点都是如此，我们将所有的子节点相加，得到的结果就是 $u$ 的价值，有：

$$f[u][0]=\sum_{i=1}^{n}\min(f[son_i][1],f[son_i][2])$$

当 $k=1$ 时，说明 $u$ 的子节点被选择，由于我们是求 $u$ 的价值，因此不需要去考虑 $u$ 的父节点的情况

我们设被选择的子节点的编号为 $t$ ，对于 $t$ 是必须要选择的，对于其他的子节点可选可不选，有：

$$f[u][1]=\sum_{i=1且i\ne t}^{n}\min(f[son_i][1],f[son_i][2])+f[son_t][2]$$

在实际实现中，由于 $f[u][1]$ 求的是所有子节点的 $min(f[son_i][1],f[son_i][2])$ 的加和，因此我们可以通过枚举所有的子节点，然后用 $f[u][0]$ 减去 $min(f[t][1],f[t][2]$ 再加上 $f[t][2]$ ，由于我们枚举了所有的子节点，因此我们需要对 $f[u][1]$ 不断取最小值

当 $k=2$ 时，对于所有的子节点，同样是可选可不选，但不选的情况有两种，即：$f[son][1]$ 与 $f[son][0]$ ，即 子节点的子节点被选择导致该子节点不会被选择 和 子节点的父节点（也就是 $u$）被选择导致该子节点不会被选择

所以这里是三个取最小值，并且要对所有的子节点加和，即：

$$f[u][2] = \sum_{i=1}^{n}\min (f[son_i][0],f[son_i][1],f[son_i][2])$$

完整代码：

#include <iostream>
#include <cstring>

using namespace std;
const int N = 1510;
int h[N], e[N], w[N], ne[N], idx;
int n;
bool st[N];
int f[N][3];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
    f[u][2] = w[u];
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += min(f[j][1], f[j][2]);
        f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
    }
    f[u][1] = 0x3f3f3f3f;//这里要给初值
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        f[u][1] = min(f[u][1], f[u][0] - min(f[j][1], f[j][2]) + f[j][2]);
    }
}
int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n; i++)
    {
        int id, cost, cnt;
        cin >> id >> cost >> cnt;
        w[id] = cost;
        while(cnt--)
        {
            int ver;
            cin >> ver;
            add(id, ver);
            st[ver] = true;
        }
    }
    int root = 1;
    while(st[root]) root++;
    dfs(root);
    cout << min(f[root][1], f[root][2]) << endl;
    return 0;
}