强制在线做法 \(O(n \log n)\)
考虑每一次标记点：只会影响其子树中的点
所以使用DFS序+线段树就可以辣！
离线做法 \(O(n \log n)\)
考虑将每一次标记的时间记录到点上
然后使用倍增 \(LCA\) 的思想向上倍增
离线做法 \(O(n\alpha(n))\)
考虑离线之后进行逆序操作
这样的话，操作就变成了删除标记
这个可以形象地想成：打通了向上走地道路
于是使用并查集即可
bzoj#4551. [Tjoi2016&Heoi2016]树
发布时间 2023-09-26 21:00:17作者: FOX_konata