526互联

bzoj#4551. [Tjoi2016&Heoi2016]树

发布时间 2023-09-26 21:00:17作者: FOX_konata

原题(需要魔法)

原题(不需魔法)

强制在线做法 \(O(n \log n)\)

考虑每一次标记点：只会影响其子树中的点

所以使用DFS序+线段树就可以辣！

离线做法 \(O(n \log n)\)

考虑将每一次标记的时间记录到点上

然后使用倍增 \(LCA\) 的思想向上倍增

离线做法 \(O(n\alpha(n))\)

考虑离线之后进行逆序操作

这样的话，操作就变成了删除标记

这个可以形象地想成：打通了向上走地道路

于是使用并查集即可