比赛 |
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;
}