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