RainAir
My OI Blog
RainAir
「HAOI2015」树上操作

题目链接

这一道题的题解在luogu上的链接

解题报告

这一题是树链剖分的板子题。

什么?你不会树链剖分?点这里学习

对于操作1:直接在点的dfn在线段树的位置修改即可。

对于操作2:我们考虑在记录每个以该点为根的子树大小时,由于dfn的顺序一定是子树的dfn小于根的,所以修改子树可以转化为修改对应的线段树中该点的 $dfn$ 与 $dfn+size−1$ (读者可以自己模拟一下)。

对于操作3:查询1到该点的距离即可。

# 代码实现

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/107
如文中无特殊声明,本文采用 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

「HAOI2015」树上操作
题目链接 这一道题的题解在luogu上的链接 解题报告 这一题是树链剖分的板子题。 什么?你不会树链剖分?点这里学习 对于操作1:直接在点的dfn在线段树的位置修改即可。 对于操作2…
扫描二维码继续阅读
2018-07-12
标签
近期评论