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