题解：P9067 [Ynoi Easy Round 2022] 虚空处刑 TEST_105

残阳如血 · 2025-07-19 11:39:03 · 题解

题意

给定一颗 n 个点的树，点有点权 a_i。

定义结点 x 的「同权连通分量」表示一个连通分量，其中每个点的点权均相等。

共有 m 次操作：

• 将结点 x 的点权修改为 y。
• 查询结点 x 所在的「同权连通分量」的大小。

记 A=\max\{a_i\}，则 n,m,A\le10^6。

解法

「同权连通分量」显然不好直接维护，考虑 dsu on tree。

注意到集合大小不减，那么可以直接合并集合。那么就可以用并查集维护每个连通分量的根结点，那么更新信息只需要处理一个点。

定点 1 为根结点，然后记 S_{u,i} 表示 u 所在的「同权连通分量」下面直接相连的颜色为 j 的结点集合。

同时维护一下每个连通分量的大小，这样子对于查询操作可以 O(1) 输出。

然后对于修改操作，具体如下：

1. 先找到对应连通分量根结点；
2. 再在 S 中启发式合并颜色相同的结点；
3. 若当前连通分量根结点的父亲颜色相同，那么也同时合并。

时间复杂度

可以发现时间复杂度的瓶颈就是合并每个集合，如果使用线性数据结构维护集合，那么单个元素的操作次数是 O(1) 的。

将所有合并的情况建成一颗树，那么一个结点需要合并到另外一个集合中当且仅当经过了一条轻边。而经过轻边后集合大小至少会翻倍（重儿子大小大于轻儿子），所以至多会经过 O(\log n) 条轻边。

故时间复杂度 O(n\log n)，预期得分 100。