题解

每次开关的是一组灯，同组的灯不一定挨在一起．如果每次都去找亮灯形成了几个区域，很容易重复遍历整棵树．我们先看看，有没有不找连通块也能数出答案的办法．

先直接统计

对子任务 1，记录每个组是否打开．一次操作后，从每个尚未访问的亮灯出发 DFS，只沿两端都亮着的通道走．启动了几次 DFS，就有几个照明区域．

一次操作遍历 $O(n)$ 个点和边，总时间 $O(nq)$，空间 $O(n)$．它可以通过子任务 1，得到 20 分．

子任务 3 还有另一条路：每个组只操作一次，灯只会亮起，不会熄灭．将这次新亮起的灯逐个加入并查集，每加入一盏灯，答案加一；它与已经亮起的邻灯连边时，如果两个连通块不同，就合并并将答案减一．

同组的灯也要逐个处理．先将当前这盏灯标记为亮，再检查它的邻居，这样一条边只会在后加入的端点处被处理．整个过程中，每个点最多加入一次，每条边最多被检查两次，总时间 $O(n\alpha(n)+q)$，空间 $O(n)$．这条做法通过子任务 3，得到 15 分；与小规模 DFS 分情况处理，可以得到 35 分．

树上不必真的维护连通块

只保留亮灯和两端都亮着的边，得到的一定是森林．每棵树的点数恰好比边数多一，因此把所有连通块加起来，有

没有亮灯时，两项都是零，这个式子也成立．现在只需要维护点和边的贡献，不需要支持删除边的并查集．

同组的灯永远同时亮、同时灭．假设第 $c$ 组有 $V_c$ 盏灯，组内有 $I_c$ 条边，那么打开这一组时，这些点和组内边一共贡献

组内的灯即使分散在几个地方也没关系，这个式子统计的是它们的总贡献，并没有把整组当成一个连通块．

还剩跨组边．记第 $c,d$ 两组之间的边数为 $E_{c,d}$．只有这两组都打开，这些边才会被减去．同一对组之间可能有多条边，必须保留这个数量，不能简单去重．

考虑打开第 $c$ 组．点和组内边带来 $W_c$ 的增加，通向已打开组的跨组边带来减少．所以本次变化是

关闭时，上面这些贡献恰好全部撤销，变化取相反数即可．邻组的状态并没有改变，所以打开和关闭可以用同一个求和式．

对每个组，存一份不同邻组及对应边数的列表．一次操作直接扫描该组的列表就能算出变化．预处理时将跨组边按组号对排序，相同组号对合并并记录次数，总时间 $O(n\log n)$，空间 $O(n)$．

子任务 2 中，实际出现的组不超过 20 个，一个组至多有 19 个不同邻组；操作空组时答案不变．每次扫描 $O(20)$ 项即可，总时间 $O(n\log n+20q)$．也可以先将这些组重新编号，直接用小矩阵统计边数，将预处理降到 $O(n)$．

子任务 4 中，一个组至多有 30 条外接通道，不同邻组更不会超过 30 个．同样的扫描做法，总时间 $O(n\log n+30q)$．

小规模数据也能用这套做法．再看子任务 3：每个组只操作一次，所以每份邻组列表最多扫描一次，所有列表加起来只有 $O(n)$ 项．因此直接扫描邻组同样可以通过子任务 3，并不一定要另写并查集．

这套中间做法可以通过子任务 1、2、3、4，共 65 分．前面的并查集是另一种利用“只亮不灭”的做法，可以在还没有想到点数减边数时拿到对应分数．

邻组很多的组，提前维护这个和

直接扫描哪里会慢？一棵星形树，每盏灯各属一组，中心灯那一组的列表就有 $n-1$ 项．反复开关中心灯，会退化成 $O(nq)$．注意，中心组只有一盏灯，所以不能按组里的灯数来决定要不要优化．

我们按不同邻组的数量分类．设阈值为 $B$，不同邻组不少于 $B$ 个的组叫重组，其余叫轻组．

所有跨组边合并以后，组间边的条数不会超过原树的 $n-1$ 条边．所有组的不同邻组数量之和因此不超过 $2(n-1)$，所以重组最多有 $2(n-1)/B$ 个．

轻组仍然现算：扫描它的邻组列表，最多不到 $B$ 项．

对重组 $h$，保存

这样操作一个重组时，可以直接取出需要的和．关键在于，其他组开关后怎样更新它？

如果组 $c$ 被打开，那么对于与它相邻的每个重组 $h$，将 $\operatorname{sum}_h$ 加上 $E_{c,h}$；关闭则减去．提前给每个组另存一份“与它相邻的重组及边数”，操作后只扫描这份列表．列表长度不会超过全体重组数量，也就是 $O(n/B)$．

因此，一次操作按下面顺序进行：

1. 轻组扫描邻组，重组读取缓存，得到通向已打开邻组的边数．
2. 用 $W_c$ 减去这个边数．打开时加到答案上，关闭时从答案中减去．
3. 切换本组状态，并更新与它相邻的重组的缓存．

一开始所有灯都熄灭，答案和所有缓存都是零．以后每次操作，仅改变当前组的点、组内边及其跨组边的贡献，第二步恰好算全这些变化．第三步又恰好更新所有受到影响的重组缓存，因此答案和缓存始终正确．

每次操作耗时 $O(B+n/B)$，取 $B$ 为 $\sqrt{2n}$ 附近的整数，总时间为

空间为 $O(n)$．两份邻接表都只保存实际存在的组间边，不需要开“组数乘重组数”的二维数组．完整做法通过全部子任务，得到 100 分．

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> c(n + 1), w(n + 1), on(n + 1);
    for (int i = 1; i <= n; ++i) { cin >> c[i]; ++w[c[i]]; }
    vector<pair<int, int>> edges;
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        u = c[u]; v = c[v];
        if (u == v) --w[u];
        else { if (u > v) swap(u, v); edges.push_back({u, v}); }
    }
    sort(edges.begin(), edges.end());
    vector<vector<pair<int, int>>> g(n + 1), heavy(n + 1);
    for (int i = 0, j; i < (int)edges.size(); i = j) {
        j = i + 1;
        while (j < (int)edges.size() && edges[j] == edges[i]) ++j;
        int u = edges[i].first, v = edges[i].second, cnt = j - i;
        g[u].push_back({v, cnt}); g[v].push_back({u, cnt});
    }
    int bound = max(1, (int)sqrt(2.0 * n));
    vector<int> large(n + 1), sum(n + 1);
    for (int u = 1; u <= n; ++u) large[u] = (int)g[u].size() >= bound;
    for (int u = 1; u <= n; ++u)
        for (auto e : g[u])
            if (large[e.first]) heavy[u].push_back(e);
    int ans = 0;
    while (q--) {
        int u; cin >> u;
        int near = 0;
        if (large[u]) near = sum[u];
        else for (auto e : g[u]) near += e.second * on[e.first];
        int sign = on[u] ? -1 : 1;
        ans += sign * (w[u] - near);
        on[u] ^= 1;
        for (auto e : heavy[u]) sum[e.first] += sign * e.second;
        cout << ans << '\n';
    }
    return 0;
}