Luogu4775 [NOI2018] 情报中心

题意 ：给出一棵 个点的树，边有正边权。

给出树上的 条路径，每条路径有一个花费。

选出两条路径，使得两条路径至少有一条公共边，且两条路径的并的边权和减去花费和最大。或指出不存在满足要求的方案。

多组数据，，，，。时限 。

---

本大胖题的阳间做法，不用分类讨论了！

对于给出的花费为 的路径 ，我们记 。

可能的两种合法方案如图。对于两种情况，收益的两倍均为 ：

考虑枚举 （即相交部分最深的点）

然后求出最大的

还要加上此时已确定的 。

这可以看做将 的权值定为 ，而 的权值定为 。

选择 两者配对的贡献为 。

这是经典的树上（带权）最远点对问题，有结论 ：

• 记 为树上点集 的最远点对。

  对于 ，有

  可见 Luogu2056 [ZJOI2007]捉迷藏。

利用这个结论，只需计算 次两点距离，就能合并点集最远点对，或者计算两个点集之间的最远点对。

使用 ，这个复杂度就是 。

记 为子树内的路径提供的匹配候选点集。

对于 ，要计算 的各个子分支之间的贡献。

对于路径 ，记 。则 会出现在 中， 会出现在 中。

它们不能出现在 的祖先的 中，否则会产生错误的匹配。

使用树上差分，我们在 点加入，在 到 的路径上的倒数第二个点删除。

用线段树合并维护，在合并时即可获得不同子分支之间的贡献。

复杂度 。