自动搬运

查看原文

来自洛谷，原作者为

	Forge_Unique 这个家伙不懒，忙的没空留下什么东西。||使命，florr玩家

搬运于2025-08-24 22:38:10，当前版本为作者最后更新于2024-10-01 16:27:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

首先考虑处理出二元组 $(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