题解 CF1458F 【Range Diameter Sum】
YLWang
·
·
题解
题意简述
给定一颗树。求 \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)。
### 题解
这里需要引入一套树上圆理论。感觉这样解释应该是最直观的。
我们考虑把树上的一些点看成坐标系上的一些点。直径就是覆盖他们最小圆的直径。
那么圆心就是树上所有直径的中点，半径就是直径的一半。
两个圆合并可以采用平面坐标系上圆合并的理论。
以下为了表述方便使用 $(v, r)$ 来表示一个圆。
$C_1 + 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)。这是个简单点分树练习题。于是板子一拉就写完了。
这份代码写的挺生草的，调得不成样子了，看看就好。
Upd : 题意简述有个小锅已经改了