比赛 |
2025.5.5 |
评测结果 |
AAAAAAATTT |
题目名称 |
终末鸟 |
最终得分 |
70 |
用户昵称 |
徐诗畅 |
运行时间 |
34.765 s |
代码语言 |
C++ |
内存使用 |
370.69 MiB |
提交时间 |
2025-05-05 11:20:36 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,q,cnt,head[N],sta[N];
vector<int> ed[N];
int vis[N];
void dfs(int u,int fa){
vis[u]=1;
for(int i = 0;i<ed[u].size();i++){
int v=ed[u][i];
if(v==fa||sta[v]==0) continue;
dfs(v,u);
}
}
int ans=0;
int main(){
freopen("birds.in","r",stdin);
freopen("birds.out","w",stdout);
scanf("%d",&n);
for(int i= 1;i<n;i++){
int u,v; scanf("%d%d",&u,&v);
ed[u].push_back(v); ed[v].push_back(u);
}
for(int i = 1;i<=n;i++) scanf("%d",&sta[i]);
for(int i = 1;i<=n;i++){
if(sta[i]&&!vis[i]){
ans++; dfs(i,0);
}
}
printf("%d\n",ans);
scanf("%d",&q);
while(q--){
int u; scanf("%d",&u);
if(sta[u]==0){
sta[u]=1;
int sum=0;
for(int i = 0;i<ed[u].size();i++)
if(sta[ed[u][i]]) sum++;
ans-=(sum-1);
}
else{
sta[u]=0;
int sum=0;
for(int i = 0;i<ed[u].size();i++)
if(sta[ed[u][i]]) sum++;
ans+=(sum-1);
}
printf("%d\n",ans);
}
return 0;
}