树上圆理论

设 \(f(u,r) = \{ v | dis(u,v) \le r \}\)，可以将其视作以 \(u\) 为圆心，\(r\) 为半径的圆。

有若干与欧几里得空间的圆相同的性质。

设点集 \(S\) 的直径长度为 \(d(S)\)，中点为 \(m(S)\)，设 \(c(S) = f(m(S), \dfrac{d(S)}{2})\)，可以视作 \(S\) 的最小覆盖圆。

Lemma : 若点集 \(S \subseteq f(u,r)\)，则 \(c(S) \subseteq f(u, r)\)。

Proof : 显然 \(r \ge dis(m(S),u) + \dfrac{d(S)}{2}\)。

则合并点集 \(S\) 和 \(T\) 的直径可以刻画为：

• 若 \(c(S) \subseteq c(T)\)，则 \(c(S \cup T) = c(T)\)。
• 若 \(c(T) \subseteq c(S)\)，则 \(c(S \cup T) = c(S)\)。
• 否则 \(c(S \cup T) = f(u, \dfrac{dis(m(S),m(T))}{2} + \dfrac{d(S) + d(T)}{4})\)，其中 \(u\) 是新的直径中点。本质和欧几里得空间的两个圆合并相同。

可以看出该体系下合并直径更加清新，无需进行传统做法的讨论。

判定 \(c(S) \subseteq c(T)\) : \(\dfrac{d(T)}{2} \ge dis(m(S),m(T)) + \dfrac{d(S)}{2}\)。

CF1458F Range Diameter Sum

考虑分治，设 \(S = [i, mid]\)，\(T = (mid, j]\)。若固定 \(S\)，则 \(T\) 在某个前缀贡献是 \(d(S)\)，中间是 \(dis(m(S), m(T)) + \dfrac{d(S) + d(T)}{2}\)，后缀是 \(d(T)\)，三部分都容易计算。