DFS 序 4

发布于 2022-10-21 | 标签: dfs 序 | 1分钟 | 107字数

维护点到根的链的权值和。

当 $x$ 的权值 $+w$ 时， $x$ 的子树中每一个点的权值要加 $w$ 。

当 $x$ 的子树权值全加 $w$ 时，令子树中有点 $y$ ，则他的权值加上 $w(dep_y-dep_x+1)$ ，即 $w\times dep_y-w\times (dep_x-1)$ 。预处理下 $x$ 子树中 $dep$ 之和即可。

召唤看板娘

感谢您的支持，我会继续努力的!