比赛 2025.5.5 评测结果 AAAAAAATMM
题目名称 终末鸟 最终得分 70
用户昵称 darkMoon 运行时间 26.866 s
代码语言 C++ 内存使用 362.80 MiB
提交时间 2025-05-05 08:32:12
显示代码纯文本
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto IN = freopen("birds.in", "r", stdin);
auto OUT = freopen("birds.out", "w", stdout);
auto IOS = ios::sync_with_stdio(false);
auto CIN = cin.tie(nullptr);
int mread(){
    int x = 0, f = 1;
    char c = cin.get();
    while(c < '0' || c > '9'){
        if(c == '-'){
            f = -1;
        }
        c = cin.get();
    }
    while(c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = cin.get();
    }
    return x * f;
}
const int N = 1e7 + 5;
int n = mread();
vector<int> v[N];
int ans = 0;
bool e[N];
int fa[N];
int s[N];
void dfs(int x, int fa){
    ::fa[x] = fa;
    for(int y : v[x]){
        if(y == fa){
            continue;
        }
        dfs(y, x);
    }
    return;
}
void add(int x){
    e[x] = 1;
    int tmp = s[x];
    if(fa[x]){
        tmp += e[fa[x]];
        s[fa[x]] ++;
    }
    ans += 1 - tmp;
}
void del(int x){
    e[x] = 0;
    int tmp = s[x];
    if(fa[x]){
        tmp += e[fa[x]];
        s[fa[x]] --;
    }
    ans -= 1 - tmp;
}
signed main(){
    for(int i = 1, x, y; i < n; i ++){
        x = mread(), y = mread();
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    for(int i = 1, x; i <= n; i ++){
        x = mread();
        if(x){
            add(i);
        }
    }
    cout << ans << "\n";
    int q = mread();
    while(q --){
        int x = mread();
        if(e[x]){
            del(x);
        }
        else{
            add(x);
        }
        cout << ans << "\n";
    }
    return 0;
}