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

题意

给定一颗

n

个点的树，点有点权

a_i

。

定义结点

x

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

m

次操作：

记

A=\max\{a_i\}

，则

n,m,A\le10^6

。

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

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

定点

1

为根结点，然后记

S_{u,i}

表示

u

所在的「同权连通分量」下面直接相连的颜色为

j

的结点集合。

同时维护一下每个连通分量的大小，这样子对于查询操作可以

O(1)

输出。

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

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

O(1)

的。

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

O(\log n)

条轻边。

故时间复杂度

O(n\log n)

，预期得分

100

。