CF1458F Range Diameter Sum

发表于 分类于 ， ， 阅读次数：

题意：给出一棵 个点的树，设 为点集 的直径长度。求

，时限 。

前置知识

点集直径：给出点集 ，找出 使得 最大，则路径 称为 的点集直径。

点集最远点：定义 。

  • 性质1： 对应的 一定是点集直径的两个端点之一。（反证）

  • 性质2：点集 的直径为 ，则 的直径一定在 四个点当中。（注意到交叉贡献一定是 far，故一定是直径端点对直径端点）

因此，计算 次树上距离就能合并点集直径。我们可以用线段树维护点集直径（Luogu2056）

  • 性质3：所有点集直径的中点（可能在边上）相同。（反证）

  • 性质4：记 的点集直径长度为 ，中点为 ，则 。

练习题：Luogu3304，CF516D。

题解

可以合并点集直径，但 种情形过于繁琐，不便考虑。

因为只需要长度，可以改用（直径中点 ，半径 ）来刻画点集直径。为了避免讨论，在每条边上插入一个点，这样直径中点一定在点上。

考虑如何合并两个点集，由于我们可以只关心这两个属性，所有点集合在我们眼里都是邻域（圆），即距离 不超过 的点的集合。合并 时：

  • ：一者包含另一者，即 ，返回后者。（反之同理）
  • 两者互不包含：直径长度为 ，形如 ，中点一定在 之间，且距离可以确定，容易倍增找出。

我们已经有了一套用 合并直径的理论，它需要分三类讨论。现在来观察本题：

使用猫树分治，设中点为 ，从 往左右预处理合并后的结果。枚举右端点 统计所有左端点 的贡献，即 需要讨论 和 的合并方式。可以发现，随着 的减小（集合 的增大）：

  • 首先， 的圆包含 的圆；
  • 然后，两圆互不包含；
  • 最终， 的圆包含 的圆。

注意到，随着 的增大（集合 增大），这两条分界线单调右移，所以可以单调扫描。

得出分界线后，统计答案时需要计算 状物，它是 Luogu4211 [LNOI2014]LCA。

复杂度 或 。（视你的树上数据结构而定）