题目大意:
有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:
题目解法:
不用树剖。
看到查询我们就想到用线段树维护每个点到根的距离单调查询。
操作1显然是x节点子树的所有点+a。所以处理dfs序。
操作2,对于x为根的子树内的任意节点v, 它在线段树中的值的增量为a*(dep[v]-dep[x]+1)。但我们显然不可以直接这样整因为我们要做的是区间修改是需要打lazy tag的。所以我们改变一下形式,每次这样的操作对于v的影响为:dep[v]系数+a, 再加上一个常数a*(1-dep[x])。因此我们开两个线段树分别维护每个点u的dep[u]系数和常数项即可。操作1显然只是加一个常数a。
复杂度O(n log n)
原文:https://www.cnblogs.com/myrcella/p/13034743.html