题解：P8339 [AHOI2022] 钥匙

· · 题解

思路

首先考虑处理出二元组 (key,box) 表示从带有钥匙的点 key 到达带有同色宝箱的点 box 的路径，且该路径满足：是用 key 处的钥匙开 box 处的宝箱。

处理方法：

由于每个颜色之间互不影响，所以我们枚举颜色 color，建立以颜色为 color 的点为关键点的虚树。

路径要满足用 key 处的钥匙开 box 处的宝箱，也就是该路径上到达 box 时钥匙和宝箱数第一次相等。

所以我们枚举颜色为 color 的钥匙点 key 作为虚树的根节点开始遍历虚树，过程中记录钥匙数，遇到同色钥匙点 +1，遇到同色宝箱点 -1。

如果过程中到 box 点钥匙数变为0，那么记录下该路径 (key,box) 后返回。

由于钥匙数不超过 5 所以所有满足条件的路径不超过 5n。

显然如果旅行 (s,e) 包含路径 (key,box) 那么路径 (key,box) 就会对该旅行有贡献，那么考虑将旅行离线下来后，路径 (key,box) 会对哪些旅行 (s,e) 做贡献。

当 key,box 中不存在一个点是另一个点的祖先时：

显然，当 s 位于 key 的子树中且 e 位于 box 的子树中时会有贡献。

当 key 是 box 的祖先时：

记路径 (key,box) 的第二个点为 u (即 key 向 box 方向走一条边到达的点)。

显然，当 s 不位于 u 的子树中且 e 位于 box 的子树中时会有贡献。

当 box 是 key 的祖先时同理。

由于一个点的子树内所有点的 dfs 序构成一段连续的区间。

将旅行 (s,e) 以 s,e 的 dfs 序分别作为横，纵坐标从而看成点，则上述在子树内的条件可以看成在平面上的一个矩形(一点是另一点祖先的情况可以看成一个大矩形减一个小矩形)。

所以问题转化为查询一个点位于多少个矩形中，这在平面上用扫描线做，并进行单点查询即可完成。

总时间复杂度：O((n+m) \log n)。

代码

code