「Luogu P3603」雪辉
题目链接题目大意给定一棵树，每个点有一个权值，每次询问给你一些链，求这些链的并上的所有点的点权中有多少种不同的点权和这些点权的 mex。题解首先我们考虑如何做一条链的情况。发现我们可以分块，对于每一个块都维护一下这个块中所有的权值的集合，只需要用能求并的结构（例如 bitset）维护就可以了。查询的时候仍然是整块暴力边角二分。 然后我们考虑放在树上：我们可以随机钦定 $\sqrt{n}$ 个...
题目链接题目大意给定一棵树，每个点有一个权值，每次询问给你一些链，求这些链的并上的所有点的点权中有多少种不同的点权和这些点权的 mex。题解首先我们考虑如何做一条链的情况。发现我们可以分块，对于每一个块都维护一下这个块中所有的权值的集合，只需要用能求并的结构（例如 bitset）维护就可以了。查询的时候仍然是整块暴力边角二分。 然后我们考虑放在树上：我们可以随机钦定 $\sqrt{n}$ 个...