比赛 2025.5.5 评测结果 C
题目名称 终末鸟 最终得分 0
用户昵称 彭欣越 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2025-05-05 11:58:57
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=10000010;
int n,q,a[N],mk[N],ans;
int head[N],tot;
struct edge {
	int v,nxt;
}e[N*2];
void add (int u,int v) {
	e[++tot].v=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}

int main () {
	freopen("birds.in","r",stdin);
	freopen("birds.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i=1;i<n;i++) {
		int x,y;
		cin >> x >> y;
		add(x,y);
		add(y,x);
	}
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=n;i++) {
		if (a[i]&&!mk[i]) {
			dfs(i); 
			ans++;
		}
	}
	cout << ans <<"\n";
	//ans=0;
	cin >> q;
	while (q--) {
	    memset(mk,0,sizeof(mk));
		int x;
		cin >> x;
		if (a[x]==0) a[x]=1;
		else a[x]=0;
		int sum=0;
		for (int i=head[x];i;i=e[i].nxt) {
			int v=e[i].v;
			if (a[v]) sum++;
		}
		if (a[x]) {
			if (sum==0) ans++;
			else if (sum==2) ans--;
		}else{
			if (sum==0) ans--;
			else ans++;
		}
		cout << ans <<"\n";
		//ans=0;
	}
	return 0;
}