RainAir
My OI Blog
RainAir
月下毛景树

题目链接

题目描述

给定一棵 $ N $ 个节点的树,需要维持以下个操作:

  1. 改变第 $ k $ 条边的边权;
  2. 改变点 $ u $ 到点 $ v $ 的边权为 $ w $;
  3. 将点 $ u $ 和点 $ v $ 路径上的边的边权都增加 $ w $;
  4. 询问点 $ u $ 和点 $ v $ 路径上的边权最大值。

其中 $ 1 \leq N \leq 10^5 $,操作+询问数目不超过 $ 10^5 $。

解题报告

这显然是树链剖分板子题。

不过这里处理的是边权,我们对于每一个边,将边权放在深度更大的点上。

然后查询的时候特判 LCA 情况(因为 LCA 不被计算)就可以了。

操作一:线段树直接找这条边深度更深的点并修改。

剩余操作全都特判 LCA 情况即可,具体可参考代码。

代码

~~我就知道你们想看这个~~

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/66
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

月下毛景树
题目链接 题目描述 给定一棵 $ N $ 个节点的树,需要维持以下个操作: 改变第 $ k $ 条边的边权; 改变点 $ u $ 到点 $ v $ 的边权为 $ w $; 将点 $ u $ 和点 $ v $ 路径上的边的边…
扫描二维码继续阅读
2018-08-22
标签
近期评论