| 比赛 | 
    2025.5.5 | 
    评测结果 | 
    AAAAAAAAAA | 
    | 题目名称 | 
    终末鸟 | 
    最终得分 | 
    100 | 
    | 用户昵称 | 
    健康铀 | 
    运行时间 | 
    20.598 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    178.68 MiB  | 
    | 提交时间 | 
    2025-05-05 11:15:31 | 
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int MX = 1e7 + 5;
struct E {
    int t, n;
} e[2 * MX];
int h[MX], ec = 0;
int p[MX];
int s[MX];
int c[MX];
void ae(int u, int v) {
    e[++ec].t = v;
    e[ec].n = h[u];
    h[u] = ec;
    e[++ec].t = u;
    e[ec].n = h[v];
    h[v] = ec;
}
int main() {
	freopen("birds.in","r",stdin);
	freopen("birds.out","w",stdout);
    int n;
    scanf("%d", &n);
    memset(h, 0, sizeof(h));
    ec = 0;
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        ae(x, y);
    }
    queue<int> q;
    q.push(1);
    memset(p, 0, sizeof(p));
    p[1] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; i; i = e[i].n) {
            int v = e[i].t;
            if (v != p[u]) {
                p[v] = u;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &s[i]);
    }
    memset(c, 0, sizeof(c));
    for (int x = 1; x <= n; ++x) {
        if (s[x]) {
            int pa = p[x];
            if (pa != 0) {
                c[pa]++;
            }
        }
    }
    int ans = 0;
    for (int x = 1; x <= n; ++x) {
        if (s[x] == 1) {
            int pa = p[x];
            if (pa == 0 || s[pa] == 0) {
                ans++;
            }
        }
    }
    printf("%d\n", ans);
    int qn;
    scanf("%d", &qn);
    while (qn--) {
        int x;
        scanf("%d", &x);
        if (s[x] == 0) {
            s[x] = 1;
            int pa = p[x];
            if (pa != 0) {
                c[pa]++;
            }
            int d = (pa == 0 || s[pa] == 0) ? 1 : 0;
            d -= c[x];
            ans += d;
        } else {
            s[x] = 0;
            int pa = p[x];
            if (pa != 0) {
                c[pa]--;
            }
            int d = (pa == 0 || s[pa] == 0) ? -1 : 0;
            d += c[x];
            ans += d;
        }
        printf("%d\n", ans);
    }
    return 0;
}