自动搬运

查看原文

来自洛谷，原作者为

	梦梦子 **

搬运于2025-08-24 22:18:28，当前版本为作者最后更新于2020-03-12 08:47:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

记$c(x,y)​$表示边权。

对$T_2$进行点分治

设$x,y$在当前点分树中到根的距离为$dep_x,dep_y$

那么我们可以认为$(x,y)$的边权为$dist_1(x,y)+dep_x+dep_y$

因为，若在当前点分树中，$lca(x,y)$等与点分树的重心，那么上式是成立的，否则$c(x,y)\leq dist_1(x,y)+dep_x+dep_y$

真实的$c(x,y)$会递归进下一个点分树被考虑到，我们可以认为这个式子依然成立，对答案不会有影响

那么我们希望在当前点分树的意义下删除一些一定不会对最终答案有贡献的$(x,y)$

考虑以下算法：

1.首先求出当前点分树中的点，在$T_1$当中的虚树。

2.对于所有当前点分树中的点$x$,建立新点$x'$,在虚树上加一条$(x,x')$边，边权为$dep_x$，我们称$mp[x']=x$,我们称所有这样的$x'$为源点

3.跑两遍树$dp$,对于虚树上每个点$y$，记录$pre[y]$表示离$y$最近的源点（如果有多个最近的随便记一个即可），$dist[y]$表示$pre[y]$与$y$的距离

4.枚举虚树中每一条边$(a,b)$，将$(mp[pre[a]],mp[pre[b]],dist[a]+dist[b]+l(a,b))$，$l$表示虚树上一条边的长度。这条边加入候选边集

所有点分树的所有候选边集大小总共$O(n\log n)$，对这些边进行$kruskal$算法，即可算出答案。

使用预处理$ST$表求$lca$可在$O(n\log n)$选出候选边集。

算法正确性证明请读者自行思考。

算法复杂度$O(n\log n+n\log n\log (n\log n))$

后面那第二个$\log$只是给$n\log n$条边排序的复杂度，众所周知$sort$排序是很快的，因此此算法可在一定意义上认为是$O(n\log n)$。$std$是基于这种做法，因此很多使用$boruvka$算法或其他做法的$O(n\log^2n)$可能会被卡常，实际上时限非常宽松。

按照此算法，$atcoder$上的那个子问题可做到$O(n)$