自动搬运

查看原文

来自洛谷，原作者为

	EastSnowLotus 向阳而生，永远热爱。喜欢聪明的人

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

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

以下是正文

好像发错号了。

为什么要过题才能发题解？

首先注意到 $s_p$ 可以表示为 $u$ 子树对应的值的和减去祖先的 lazy 之和乘上该区间的长度，所以其实只需要考虑如何维护 $\sum lz_iv_i$。

记 $P_i$ 表示 $[i,i]$ 对应节点。首先根据 zkw 线段树能够得到一个结论：线段树上区间 $[l,r]$ 所包含的线段树区间，为 $P_{l-1}$ 和 $P_{r+1}$ 在树上构成的链内部的那部分。因此一次操作相当于将链上的点（实际上两端可以认为是 $\operatorname{LCA}(P_{l-1},P_l)$ 和 $\operatorname{LCA}(P_r,P_{r+1})$）全都 pushdown，并且将这条链内侧第一层的所有点（类似一个毛毛虫的形状）全都加上 $v$。

因为 pushdown 之后的变化比较阴间，但是注意到如果我们考虑维护每个点到根的链上的 lazytag 之和，就会发现 pushdown 的时候等价于链上清空，而其他位置不会发生变化。

于是我们考虑在每个位置记录其到根的 lazytag 之和，这样当我们进行区间加的时候，实际上就等价于进行以下两个操作：

1. 将一条链上所有的 $a_i$ 改为 $0$；
2. 将一条链内部所有点的 $a_i$ 都加上 $k$；
3. 查询 $\sum (a_i-a_{f_i})v_i$。

首先查询里面那个差分的系数可以也合并进 $v_i$ 里，所以我们现在还是求 $\sum a_iv_i$。将链修改为 $0$ 是简单的，现在我们的问题是对一条从下往上的链上所有点的不在链上的左/右子树进行操作。

考虑修改一下树剖的 dfs 序：对于一条重链，先从上到下依次遍历重链上的点，接着从下往上依次遍历链上的点的轻左子树（没有就跳过），最后从下往上依次遍历链上的点的轻右子树。

于是容易发现此时一条重链上的这些子树可以用上面的顺序中 $O(1)$ 个区间来表示，于是这样我们就可以用 $O(\log n)$ 个区间来表示一条任意的从下到上的链上的这些子树。

这样直接用一个普通的区间赋值区间加求带权和的线段树维护，总时间复杂度 $O(n\log^2 n)$。