1. 题目

传送门=￣ω￣=

2. 题解

裸树型 dp
设 f1[i] 为选该节点的最小花费，f2[i] 为不选该节点的最小花费
$f1[i]=\sum{min(f1[son[i]],f2[son[i]])} + 1$
$f2[i]=\sum{f1[son[i]]}$

#include <bits/stdc++.h>
using namespace std;
int n,f1[1505],f2[1505],root,dfs1(int),dfs2(int);
vector<int> g[1505];
bool book[1505];
int main()
{
    scanf("%d",&n),memset(f1,127,sizeof(f1)),memset(f2,127,sizeof(f2));
    for(int i=1,u,a,b;i<=n;i++)
    {
        scanf("%d%d",&u,&a);
        for(int i=1;i<=a;i++)scanf("%d",&b),g[u].push_back(b),book[b]=1;
    }
    for(int i=0;i<n;i++)if(!book[i]){root=i;break;}
    printf("%d\n",min(dfs1(root),dfs2(root)));
    return 0;
}
int dfs1(int u)
{
    if(f1[u]<1e8)return f1[u];f1[u]=1;
    for(int i=0;i<g[u].size();i++)f1[u]+=min(dfs1(g[u][i]),dfs2(g[u][i]));
    return f1[u];
}
int dfs2(int u)
{
    if(f2[u]<1e8)return f2[u];f2[u]=0;
    for(int i=0;i<g[u].size();i++)f2[u]+=dfs1(g[u][i]);
    return f2[u];
}