比赛 2025.5.5 评测结果 AAAAAAAMMM
题目名称 终末鸟 最终得分 70
用户昵称 djyqjy 运行时间 20.414 s
代码语言 C++ 内存使用 362.91 MiB
提交时间 2025-05-05 09:15:01
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
inline int re()
{
    int f=1,num=0;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
    return num*f;
}
const int N=10000010;
int n,q;
vector<int> vec[N];
int f[N],d[N];
bool mark[N];
int jsq=1;
void dfs(int x,int fa)
{
    f[x]=fa;
    for(auto y:vec[x])
    {
        if(y==fa) continue;
        dfs(y,x);
    }
    return;
}
int ans;
void insert(int x)
{
    if(mark[x]==0)
    {
        ans-=d[x]+mark[f[x]]-1;
        d[f[x]]++;
    }
    else
    {
        ans+=d[x]+mark[f[x]]-1;
        d[f[x]]--;
    }
    mark[x]^=1;
    return;
}
int main()
{
    freopen("birds.in","r",stdin);
    freopen("birds.out","w",stdout);
    n=re();
    for(int i=1,x,y;i<n;i++) x=re(),y=re(),vec[x].push_back(y),vec[y].push_back(x);
    dfs(1,0);
    for(int i=1;i<=n;i++) if(re()) insert(i);
    printf("%d\n",ans);
    q=re();
    for(int i=1;i<=q;i++) insert(re()),printf("%d\n",ans);
    return 0;
}