Miku

或许dp起来有点麻烦

那何不记忆化呢

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int head[100001];
int p;
struct b{
    int to;
    int ne;
}e[100001];
int n,x,y;
int z;
int dp[100001][3];
int dfs(int now,int si,int fa){
    if(dp[now][si]>=0)
    return dp[now][si];
    dp[now][si]=0;
    if(si==0){
        for(int i=head[now];i;i=e[i].ne){
            if(e[i].to!=fa)
            dp[now][si]+=dfs(e[i].to,1,now);
        }
        return dp[now][si];
    }else{
        for(int i=head[now];i;i=e[i].ne){
            if(e[i].to!=fa)
            dp[now][si]+=min(dfs(e[i].to,1,now),dfs(e[i].to,0,now));
        }
        dp[now][si]+=1;
        return dp[now][si];
    }   
}
void add(int f,int to){
    p++;
    e[p].to=to;
    e[p].ne=head[f];
    head[f]=p;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&y);
        for(int j=1;j<=y;++j){
            cin>>z;
        add(x,z);
        add(z,x);
        }
    }
    memset(dp,-1,sizeof(dp));
    dfs(0,0,-1);dfs(0,1,-1);;
    cout<<min(dp[0][1],dp[0][0]);
    return 0;
}