比赛 2025暑期集训第4场 评测结果 E
题目名称 战略游戏 最终得分 0
用户昵称 wdsjl 运行时间 0.434 s
代码语言 C++ 内存使用 117.79 MiB
提交时间 2025-07-05 09:37:48
显示代码纯文本
#include  <bits/stdc++.h>
using namespace std;

const int N = 10000000;

int hd[N],net[N],ver[N],d[N],dp[N][3],n,idx,k,x,y,maxd,maxi,res;

void add(int x,int y){
	ver[++idx]=y;
	net[idx]=hd[x];
	hd[x]=idx;
} 

void dfs(int x,int fa){
	dp[x][1]=1,dp[x][0]=0;
	for(int i=hd[x];i;i=net[i]){
		int y=ver[i];
		if(y==fa)continue;
		dfs(y,x);
		dp[x][0]+=dp[y][1];
		dp[x][1]+=min(dp[y][0],dp[y][1]);
	}
}

int main (){
	freopen("strategic.in","r",stdin);
	freopen("strategic.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		cin>>k;
		while(k--){
			cin>>y;
			add(x,y);
			add(y,x);
		}
	}
	dfs(0,0);
	cout<<min(dp[0][1],dp[0][0]);
	return 0;
}