自动搬运

查看原文

来自洛谷，原作者为

	CYJian 今日はこっちの地方はどしゃぶりの晴天でした，昨日もずっと暇で一日満喫してました

搬运于2025-08-24 22:09:47，当前版本为作者最后更新于2019-10-15 20:28:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

关于树剖，它还活着... 大家珂以忽略那个群名片...

首先我们可以用并查集动态维护森林的连通状态，然后我们就知道了哪些边/传送门要留下。

然后考虑怎么处理传送门：

首先非常 naive 的想法是：直接树剖，剖出来之后再强上线段树优化建图

好，时间复杂度 $O(m \log^3 n)$，空间复杂度 $O(m \log^2 n)$，你人没了。。

如果你打了一个这样的 shit 出来，发现空间耗得贼大，跑到天荒地老才跑出一坨东西出来，然后又不想删掉它，你就可以想一想怎么优化它：

你可以发现，对于每个从一条剖出来的链 中间的点 到 链顶 的一段区间 连边的段数实际上是 $O(m \log n)$ 级别的。如果这里连的边数不是线段树优化的 $O(\log n)$ 而是 $O(1)$ 的话，你就赢了引用一下神仙zzq的名言。

那么怎么搞呢？

我们知道，对于一个序列，如果我们只要求这个序列的前缀信息 且不用修改 ，完全可以不用线段树维护，而是可以直接求前缀和之类的东西。这样就可以把线段树的 $O(\log n)$ 级别的信息维护转化为了 $O(1)$。

所以这样可能你就明白了：对于每一个点，我们开两个虚点，一个表示连出去的，一个表示连进来的。

然后对于连进来的，我们把一条重链上的所有这样的虚边由深度大的连向深度小的，然后串成一条链，这样我们就可以通过连向一个点的虚点来实现连向这个点对应的实点一直到链顶的这样一条链。

对于连出去的同理，方向反一下就行了。

画成一张图大概就长这样了：(1-2-3的一条链，左边是连进来的，右边是连出去的)

然后这样我们就可以实现 $O(m \log n)$ 条边了。

啥？你说最后两个点在同一个重链上的时候怎么办？？

你之前写的线段树优化建图就可以用上了。。

反正连上去也是 $O(m \log n)$ 级别的边数。

然后配上一个 ${\rm Dijsktra}$，这样复杂度就是 $O(m \log^2 n)$ 了。

代码太长了，这里就给个剪贴板的链接