RainAir
My OI Blog
RainAir
「Luogu P3603」雪辉

题目链接

题目大意

给定一棵树,每个点有一个权值,每次询问给你一些链,求这些链的并上的所有点的点权中有多少种不同的点权和这些点权的 mex。

题解

首先我们考虑如何做一条链的情况。发现我们可以分块,对于每一个块都维护一下这个块中所有的权值的集合,只需要用能求并的结构(例如 bitset)维护就可以了。查询的时候仍然是整块暴力边角二分。
然后我们考虑放在树上:我们可以随机钦定 $\sqrt{n}$ 个点为「关键点」,然后我们查询一条链 $x \to y$ 的时候我们将其分解为 $x \to lca$ 和 $y \to lca$。然后就是把路径拆成了链,把关键点看做两块之间的分界,直接爬就可以了。

注意到 STL 的 bitset 不资瓷求 mex,我们需要自己手写一个。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/570
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望中考不要翻车,希望 NOIP 不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「Luogu P3603」雪辉
题目链接 题目大意 给定一棵树,每个点有一个权值,每次询问给你一些链,求这些链的并上的所有点的点权中有多少种不同的点权和这些点权的 mex。 题解 首先我们考虑如何做一条链的情况…
扫描二维码继续阅读
2019-03-26
文章归档