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

这道题跟 AcWing 285. 没有上司的舞会 是对称的

没有上司的舞会，可以理解成每条边最多选择一个点，本题则是每条边最少选择一个点

本题的思路也是类似的，用状态机来解决

$f[u][k],\ k=0,1$ 表示：考虑以节点 $u$ 为根的子树，在处于状态 $k$ 时的所有可能的选择，属性为最小值

若 $k=0$，表示不选择节点 $u$ ，若 $k=1$，表示选择节点 $u$

由于每条边至少选择一个节点，因此如果不选当前节点，那么另一个节点必须要选择，即：

$$f[u][0]=\sum_{k=1}^{n}f[son_k][1]$$

同理，如果选择当前节点，那么另一个节点可选可不选，我们取二者的较小值即可

$$f[u][1] = \sum_{k=1}^{n}min(f[son_k][0],f[son_k][1])$$

完整代码：

#include <iostream>
#include <cstring>

using namespace std;
const int N = 3010;
int h[N], e[N], ne[N], idx;
int f[N][2];
bool st[N];
int n;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u)
{
    f[u][0] = 0, f[u][1] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += f[j][1];
        f[u][1] += min(f[j][0], f[j][1]);
    }
}

int main()
{
    while(scanf("%d", &n) != -1)
    {
        memset(h, -1, sizeof h);//要记得初始化三个
        memset(st, false, sizeof st);
        idx = 0;
        for(int i = 1; i <= n; i++)
        {
            int id, cnt;
            scanf("%d:(%d)", &id, &cnt);
            while(cnt--)
            {
                int b;
                scanf("%d", &b);
                add(id, b);
                st[b] = true;
            }
        }
    int root = 0;
    while(st[root]) root++;

    dfs(root);

    cout << min(f[root][0], f[root][1]) << endl;
    }


    return 0;
}