比赛 |
2025.5.5 |
评测结果 |
WWTTTTTEEE |
题目名称 |
终末鸟 |
最终得分 |
0 |
用户昵称 |
123 |
运行时间 |
69.902 s |
代码语言 |
C++ |
内存使用 |
78.10 MiB |
提交时间 |
2025-05-05 11:46:43 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,a[N],idx[N],nxt[N],head[N],tot=0,q,vis[N],ret=0;
void add(int x,int y)
{
idx[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int now)
{
vis[now]=1;
for (int i=head[now];i;i=nxt[i])
{
int y=idx[i];
if (a[y]==1 && vis[y]==0)
{
dfs(y);
}
}
}
int main() {
freopen("birds.in","r",stdin);
freopen("birds.out","w",stdout);
cin>>n;
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
cin>>q;
for (int i=1;i<=n;i++)
{
if (!vis[i] && a[i]==1)
{
ret++;
dfs(i);
}
}
while (q--)
{
int x;
scanf("%d",&x);
a[x]=1-a[x];
memset(vis,0,sizeof(vis));
ret=0;
for (int i=1;i<=n;i++)
{
if (!vis[i] && a[i]==1)
{
ret++;
dfs(i);
}
}
printf("%d\n",ret);
}
}