首页 > 其他 > 详细

#0017. [HAOI2015]树上操作

时间:2020-06-03 09:23:05      阅读:41      评论:0      收藏:0      [点我收藏+]

题目大意:

  有一棵点数为 N 的树,以点 1 为根,且树点有边权。然后有 M 个操作,分为三种:

  • 操作 1 :把某个节点 x 的点权增加 a 。
  • 操作 2 :把某个节点 x 为根的子树中所有点的点权都增加 a 。
  • 操作 3 :询问某个节点 x 到根的路径中所有点的点权和。

题目解法:

  不用树剖。

  看到查询我们就想到用线段树维护每个点到根的距离单调查询。

  操作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)

#0017. [HAOI2015]树上操作

原文:https://www.cnblogs.com/myrcella/p/13034743.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!