自动搬运

查看原文

来自洛谷，原作者为

	Nt_Tsumiki 火星咖啡馆 || 我们终将相遇，在那悠远的苍穹 || xp是傲娇少女 || 绀海厨子捏 || 会不定时红温 || NOIP 2024 全国唯一一个 263 || 我是粘土投诉米奇

搬运于2025-08-24 22:33:21，当前版本为作者最后更新于2025-02-04 14:57:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

CF2063E pro max 加强版。

首先分子分母分开讨论，分母可以看 link，本文主要讨论分子。

一些约定：

• $D_u,D_v$ 表示 $u,v$ 的到根路径权值和；
• $d_u,d_v$ 表示 $u$ 到 $\text{LCA}(u,v)$ 的路径权值和和 $v$ 到 $\text{LCA}(u,v)$ 的路径权值和；
• 下文若无特殊说明，默认 $u$ 为二者中深度最深的节点。

然后我们对于 $\sum d_u+d_v$ 和 $\sum x$ 先分开考虑，对于后者我们有 $x\in [d_u-d_v+1,d_u+d_v-1]$，然后先大力推一波式子：

$$\begin{aligned} \sum\sum_{x=d_u-d_v+1}^{d_u+d_v-1}x=&\sum\sum_{x=1}^{d_u+d_v-1}x-\sum_{x=1}^{d_u-d_v}x\\ =&\sum\frac{(d_u+d_v)(d_u+d_v-1)}{2}-\frac{(d_u-d_v)(d_u-d_v+1)}{2}\\ =&\sum\frac{(d_u+d_v)^2-(d_u+d_v)}{2}-\frac{(d_u-d_v)^2+(d_u-d_v)}{2}\\ =&\sum\frac{(d_u+d_v)^2-(d_u-d_v)^2}{2}-\frac{(d_u+d_v)+(d_u-d_v)}{2}\\ =&\sum 2d_ud_v-d_u \end{aligned} $$

也就是说我们对于所有合法的 $u,v$ 要去计数 $2d_ud_v-d_u$，前者是简单的 dfs 时在 LCA 处统计即可，对于后者我们有 $d_u=D_u-D_{\text{LCA}(u,v)}$，对于后一项依旧在 LCA 处统计，前一项为了方便后续统计别的贡献，所以我们考虑在 $v$ 处统计，那把所有点按到根路径从大到小排个序，对于点 $v$ 假设他在排序好的序列中排名为 $i$，那么所有的 $(u,v)$ 数为 $i-1$，不合法的也一定是 $v$ 子树中的点被算成了 $u$ 数量为 $siz_v-1$，那么带上权也一样就是前缀到根路径权的和减去子树到根路径权的和。

对于 $\sum d_u+d_v$ 注意这个 $\sum$ 把系数省了，写全点是 $\sum (d_u+d_v-1-(d_u-d_v+1)+1)\times(d_u+d_v)$，依旧推一波式子：

$$\begin{aligned} \sum (d_u+d_v-1-(d_u-d_v+1)+1)\times(d_u+d_v)&=\sum (2d_v-1)(d_u+d_v)\\ &=\sum 2d_vd_u+2d_v^2-(d_u+d_v)\\ \end{aligned} $$

对于前一项我们依旧在 LCA 处统计，最后一项也可以在 LCA 处统计，对于中间那一项由于带了一个指数，所以我们考虑拆成 $(D_v-D_{\text{LCA}(u,v)})^2=D_v^2+D_{\text{LCA}(u,v)}^2-2D_vD_{\text{LCA}(u,v)}$。

对于中间那一项依旧在 LCA 处统计，对于最后一项相当于给定 $v$ 对于所有合法的 $(u,v)$ 求出 $\sum D_{\text{LCA}(u,v)}$ 考虑 P4211 的做法，可以用树剖加线段树做到 2log，也可以用 LCT 做到 1log。

对于第一项，就是算合法 $(u,v)$ 数量，上面算 $\sum d_u$ 时提到为 $i-1-(siz_v-1)$。

综上，我们总结一下具体需要算哪些东西：

• 在 LCA 处我们要算所有合法以它为 LCA 的 $(u,v)$ 的 $\sum 4d_ud_v-(d_u+d_v)$ 以及 $\sum D_{\text{LCA}(u,v)}^2$。
• 在 $v$ 处我们要算钦定 $v$ 所有合法的 $(u,v)$ 的 $\sum -d_u+D_v^2-2D_vD_{\text{LCA}(u,v)}$。

总复杂度为 $O(n\log n)$ 或者是 $O(n\log^2 n)$，瓶颈在 P4211。

submission