自动搬运

查看原文

来自洛谷，原作者为

	zjy2008 else if

搬运于2025-08-24 22:22:41，当前版本为作者最后更新于2025-03-19 08:41:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

给一篇复杂度 $O(N+M)$ 的题解。

首先有在只走树边的情况下 $ans\le 2(n-1)-$ 直径，而走非树边必须要直径长度 $>\lceil \dfrac{N}{3}\rceil$，走 $2$ 条非树边必有长度 $\ge (n-3)+2\lceil \dfrac{N}{3}\rceil\ge 2(n-1)-(\lceil \dfrac{N}{3}\rceil+1)\ge 2(n-1)-$ 直径，一定更劣，故我们只需要考虑走一条非树边的情况。

考虑对于一条非树边 $(u,v,w)$ 和一对起终点 $(s,t)$ 如何计算答案，定义 $d(u,v)$ 为 $u,v$ 在树上的距离，$P((u,v),(s,t))$ 为 $(u,v)$ 和 $(s,t)$ 的交的长度，容易发现答案 $=2(n-1)-d(u,v)-d(s,t)+2\max(0,P((u,v),(s,t))-1)+w$。这显然可以通过 dp 实现 $O(nm)$ 得到 $64$ 分。

考虑点分治，只处理 $(u,v)$ 路径跨过分治中心的 $(u,v,w)$，显然可以通过 dp 获得需要的信息，若 $(s,t)$ 在同一子树内，可以直接用维护子树内 dp 值前 $3$ 大来解决。而分治中心比较特殊，需要维护前 $4$ 大值。实现起来会比较痛苦，可能需要比较好的封装，复杂度是线性的。

注意到当点分治到连通块大小 $\le \lceil \dfrac{N}{3}\rceil$ 时就不需要继续分治下去了，这时非树边 $(u,v,w)$ 一定有 $d(u,v)\ge w$，不优。故点分治层数至多只有 $2$ 层，复杂度是 $O(N+M)$ 的。

代码太长了，就不给了。