比赛 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;
}