题解：P7815 「小窝 R3」自傷無色
Nt_Tsumiki
·
·
题解
CF2063E pro max 加强版。
首先分子分母分开讨论，分母可以看 link，本文主要讨论分子。
一些约定：
-
-
- 下文若无特殊说明，默认 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