P9620 歌姬 题解

感觉题解做法都好神秘。

来一个容易理解，通俗易懂的树剖解法。

思路

容易发现原问题等价于维护一个虚树。

每一次询问虚树的根的所有儿子的最大值。

要求链修。

容易发现仅仅动态维护根是好做的。

我们用一个 \(\text{set}\)。

每次维护 \(\text{dfs}\) 的最小值和最大值。

对于这两个点求最近公共祖先就是整个虚树的根。

现在就只需要维护链修与儿子查询。

这就是一个经典的树剖拓展了。

我们在第二次 \(\text{dfs}\) 的时候。

我们将所有轻儿子一起遍历。

那么就可以做到每个点除了重儿子，轻儿子编号连续。

每条重链，除了链顶，其余编号连续。

与普通树剖相比常数只是乘了二。

Code

AC记录。