思路：
dp[i][0]表示第i个点不放士兵所需的最少士兵数，dp[i][1]表示第i个点放士兵所需的最少士兵数。
转移：
如果当前节点不放士兵，子节点要放士兵；如果当前节点放士兵，子节点取min。
代码：
//#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=1e6+7; ll n,h[maxn],idx; struct node{ ll e,ne; }edge[maxn]; void add(ll u,ll v){ edge[idx]={v,h[u]},h[u]=idx++; } ll dp[maxn][2]; void dfs(ll u,ll fa){ dp[u][0]=0;///不放 dp[u][1]=1; for(ll i=h[u];i!=-1;i=edge[i].ne){ int j=edge[i].e; if(j==fa) continue; dfs(j,u); dp[u][0]+=dp[j][1]; dp[u][1]+=min(dp[j][0],dp[j][1]); } } void solve(){ memset(h,-1,sizeof h); n=read; rep(t,0,n-1){ int i=read; int m=read; rep(j,1,m){ int x=read; add(x,i);add(i,x); } } dfs(0,-1); cout<<min(dp[0][0],dp[0][1])<<endl; } int main(){ int T=1; while(T--) solve(); return 0; }
