题解 CF1458F 【Range Diameter Sum】

### 题意简述 给定一颗树。求 $\sum_{i=1}^{n}\sum_{j=i}^{n} \operatorname{diam}(i, j)$。 其中 $\operatorname{diam}(l, r) = \max_{i=l, j=l}^{i=r, j=r} \operatorname{dist}(i, j)$。 $n \le 10^5$。 ### 题解 这里需要引入一套树上圆理论。感觉这样解释应该是最直观的。 我们考虑把树上的一些点看成坐标系上的一些点。直径就是覆盖他们最小圆的直径。 那么圆心就是树上所有直径的中点，半径就是直径的一半。 两个圆合并可以采用平面坐标系上圆合并的理论。 以下为了表述方便使用 $(v, r)$ 来表示一个圆。 $C_1 + C_2 = $ - $\operatorname{dist}(v_1, v_2) +\ r_1 \le r_2 \rightarrow C_2$。 - $\operatorname{dist}(v_1, v_2) +\ r_2 \le r_1 \rightarrow C_1$ - $\text{otherwise} \rightarrow (\text{go}(v_1, v_2, \dfrac{1}{2}(\operatorname{dist}(v_1, v_2) - r_1 + r_2)), \dfrac{1}{2}(\operatorname{dist}(v_1, v_2) + r_1 + r_2))$ 这里 $\text{go}(v_1, v_2, k)$ 是指在$(v_1, v_2)$ 的路径上从 $v_1$ 出发走 $k$ 步。 以上内容可以画画圆方便理解。 --- 回到题目本身。 我们考虑这类问题的普遍解法：枚举右端点，维护所有左端点的和。 但很遗憾的是你移动一次右端点就要修改所有左端点的值。这个是没法优化复杂度的。 于是我们应该想到整体处理——分治。 我们考虑计算区间 $[l, r]$ 中跨过 $mid$ 的线段的值。 定义 $C_i = (i, 0),\ L_i = \sum_{j=i}^{mid}C_j,\ R_i = \sum_{j=mid}^{i}C_j$。也就是说我们要把所有 $L$ 和 $R$ 拼起来，即计算 $\sum_{i=l}^{mid}\sum_{j=mid+1}^{r}(L_i+R_i).r$。 容易一遍循环把所有 $L, R$ 都处理出来。我们考虑枚举从右往左每个 $L$ 计算值。 然后我们惊奇地发现，$R$ 中的圆一定会被分成三段。左边一段全部为合并时的情况 $2$，中间一段全部为合并时的情况 $3$，右边一段全部为合并时的情况 $1$。而且这两个分界线都是右移的。 于是我们的问题就变成了维护一个点集 $S$，查询对于点 $u$ 的 $\sum_{v\in S} \operatorname{dist}(u, v)$。这是个简单点分树练习题。于是板子一拉就写完了。 这份[代码](http://codeforces.com/contest/1458/submission/102651166)写的挺生草的，调得不成样子了，看看就好。 #### Upd : 题意简述有个小锅已经改了