这题的题面非常的有诗意，大意就是给你一颗 $n$ 个点的树，点有点权，$m$ 和操作，操作有：
- 把 $u$ 的点权 $+\Delta$。
- 把 $u$ 所在子树的所有点权全部加上 $\Delta$。
- 在所有满足 $(x,y)$ 的 $lca$ 是 $u$ 的点对中随意选出一个，求 $w_x+w_y$ 的期望值（$w$ 为点权）。
先考虑这个奇怪的3操作。
设 $sze_u$ 表示 $u$ 所在子树的大小，$sum_u$ 表示 $u$ 所在子树所有点权之和。
那么3操作的答案即为（$v$ 是 $u$ 的儿子，$size_u$ 为 $u$ 子节点个数）
令 $f_u=(size_u^2-\sum size_v^2-1)/2,g_u=sum_u\times size_u-\sum sum_v\times size_v-w_u$
则 $f_u$ 表示有多少个点对 $(x,y)$ 满足 $x,y$ 的 $lca$ 是 $u$，$g_u$ 表示所有满足询问满足 $(x,y)$ 的 $lca$ 是 $u$ 的 $(x,y)$ 点权总和。
先 dfs 一遍求出 $f$ 和 $g$ ，接下来考虑两个修改：
单点修改
先调整 $f_u$ 的值。
然后考虑它对祖先的影响。假设 $x$ 为 $u$ 的祖先，$y$ 为 $x$ 在 $u$ 方向的儿子。
则 $sum_x$ 增加了 $\Delta$，$sum_y$ 也增加了 $\Delta$，$f_x$ 增加了 $\Delta\times (size_x-size_y)$。
暴力往上枚举每个祖先不可取，但这个 $y$ 又是根据 $x$ 的不同不断变化的，怎么办？
遇树不决，树链剖分如果 $u$ 沿着树链剖分的重链往上跳，那么由于只会经过 $\log n$ 条轻边，所以最多只有 $\log n$ 个 $u$ 的祖先 $x$ 在 $u$ 方向的儿子不是它的重儿子。
所以遇到轻边暴力调整 $f$，遇到重链用树状数组/线段树维护一下，设 $son_x$ 为 $x$ 的重儿子，则 $size_x-size_{son_x}$ 是一个定值，只需要询问的时候乘上去就可以了。所以开一颗树状数组/线段树，把一条重链在树状数组上对应的区间全部加上 $\Delta$，询问的时候再把 $f_u$ 加上树状数组中 $u$ 点的值乘上 $size_u-size_{son_u}$。
子树修改
这个操作从整体考虑，子树内的每个点的答案（注意是最后期望值的答案不是 $f$）全都加上了 $2\times \Delta$（每个点对都加上了这么多点权）。这里又要开一颗树状数组/线段树（如果是线段树其实不用新开一颗），维护一下这个子树答案的整体加。
然后对祖先的影响就是把单点修改i的 $\Delta$ 变成了 $size_u\times \Delta$，可以直接粘单点修改的代码。
查询的时候需要查询两颗线段树。
代码很短，但有一些细节。
1 |
|