P6643 题解

zjy2008 · 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) 的。

代码太长了，就不给了。