比赛 2025暑期集训第4场 评测结果 W
题目名称 战略游戏 最终得分 0
用户昵称 Hollow07 运行时间 0.136 s
代码语言 C++ 内存使用 8.62 MiB
提交时间 2025-07-05 10:12:02
显示代码纯文本
#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]=1;
	f[u][2]=2e9;
	for (auto x:v[u]) {
		if (x==fa) continue;
		dp(x,u);
		f[u][0]+=min(f[x][0],f[x][1]);
		f[u][1]+=f[x][2];
	}
	for (auto x:v[u]) {
		if (x==fa) continue;
		f[u][2]=min(f[u][2],f[u][1]+f[x][0]-f[x][2]);
	}
}

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][2]));
	}
}