记录编号	602666	评测结果	A
题目名称	2997.[POJ 1463]战略游戏	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	0.221 s
提交时间	2025-07-05 13:39:25	内存使用	8.66 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+5;

ll n,k,f[N][3],x,y;
vector<int> v[N];
char c;

void dp(int u,int fa) {
	f[u][0]=0;f[u][1]=1;
	for (auto x:v[u]) {
		if (x==fa) continue;
		dp(x,u);
		f[u][1]+=min(f[x][0],f[x][1]);
		f[u][0]+=f[x][1];
	}
}

int main(){
	freopen("strategic.in","r",stdin);
	freopen("strategic.out","w",stdout);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	while(scanf("%lld",&n)!=EOF){
		memset(f,0,sizeof f);
		for (int i=1;i<=n;i++) v[i].clear();
		for (int i=1;i<=n;i++){
			scanf("%lld:(%lld)",&x,&k);x++;
			for (int i=1;i<=k;i++){
				scanf("%lld",&y);y++;
				v[x].push_back(y);
				v[y].push_back(x);
			}
		}
		dp(1,0);
        printf("%lld\n",min(f[1][0],f[1][1]));
	}
}