[DS记录]P7581 「RdOI R2」路径权值(distance)

**题意** ： 给你一棵 $n$ 个点的边带权有根树，根节点为编号为 $1$ 的节点。 定义 $u$ 的 $\text{k-}son$ 为 $u$ 子树中向下经过 $k$ 条边能到达的所有点。 $m$ 次询问点 $u$ 的 $\text{k-}son$ 两两之间距离的和。答案对 $10^9+7$ 取模。 $n,m,k\leq 10^6$ ，时限$\texttt{2s}$。 ------------ 考虑合并两个 $\rm lca$ 为 $t$ 的点集 $S_1,S_2$ : $$ \begin{aligned} {\rm Ans}_{S_1+S_2}&={\rm Ans}_{S_1}+{\rm Ans}_{S_2}+\sum\limits_{u\in S_1,v\in S_2}dis(u,v)\\ &={\rm Ans}_{S_1}+{\rm Ans}_{S_2}+\sum\limits_{u\in S_1,v\in S_2}dep_u+dep_v-2dep_t\\ &={\rm Ans}_{S_1}+{\rm Ans}_{S_2}+|S_2|{\rm Sdep}_{S_1}+|S_1|{\rm Sdep}_{S_2}-2|S_1||S_2|dep_t \end{aligned} $$ 记 $c[u][k]$ 为 $u$ 的 $\text{k-}son$ 的个数，记 $sd[u][k]$ 为 $u$ 的 $\text{k-}son$ 的深度和，$f[u][k]$ 为 $u$ 的 $\text{k-}son$ 的距离和（答案）。 根据上面的式子，容易长剖维护，复杂度 $O(n+m)$。 ```cpp ```