今天是 Bogdan 的生日,他的母亲送给他一棵有 $n $ 个节点的树,每条边上有一个数字 $x_i $.有 $m $ 个客人参加了 Bogdan 的生日排队.第 $i $ 个客人到达后,他会进行如下 $2 $ 种操作中的恰好一种:
显然用树链剖分是可以做的,但是鉴于其码量大,常数大,以及没有利用本题的性质,再此不赘述了.接下来将介绍一种好写,复杂度优越的做法.
又因为修改是单调下降的,于是一条边的边权只可能变小.对于一条权值为 $1$ 的边,我们把他两侧的点缩起来,使用并查集即可实现.但是需要注意合并的方向:一定是深度大的点合并到深度小的点上,否则复杂度是错的.