P12462 题解

qbf！ · 2025-05-10 07:52:31 · 题解

考虑 q=1 如何线性。

我们发现直径的端点肯定要选上，然后直接长剖取前 k 大即可，这里需要用到 nth_element 函数才能线性。

对于 q\ne 1 的情况，我们类似线段树维护区间直径，每次把左右合并起来。

即，我们每个区间保留选 100 个点最大化虚树边权和时，那 100 个点是哪些。

这样合并时我们对 200 个点做一次 q=1 即可。

合并时需要建立虚树，这里需要按 dfs 序归并，还要 \mathcal O(1) LCA 才能线性。

可以把按询问离散化后的区间建线段树，这样线段树大小就是 \mathcal O(q) 了。

时间复杂度 \mathcal O(n\log n+qk\log q)。

upd：可以按 k 分块然后建 ST 表，这样复杂度就是 \mathcal O(\frac nk\times k\log n+qk)=\mathcal O(n\log n+qk)。