题目描述
给定一颗有根树,树上的点有权值。你需要完成 $m$ 次操作:
- 查询子树 $u$ 的最小点值
- 将树链 $u \to v$ 上的所有点的权值修改为 $w$
- 将根换为点 $u$
$n, m \leqslant 10^5$
算法分析
如果没有第三个操作,可以简单地用树剖加线段树解决。
换根后会发生什么?
换根后,链修改操作不会有影响。
如何查询子树最小值?
固定一个形式根,只需要考虑更换后的根的“子树”是哪些部分,然后分类讨论即可。
时间复杂度为 $\mathcal{O}(n\log^2 n)$
有一种数据结构叫 $\operatorname{Link} ~ \operatorname{Cut} ~ \operatorname{Tree}$,可以在 $\mathcal{O}(n\log n)$ 的时间内解决这个问题。