自动搬运

查看原文

来自洛谷，原作者为

	qbf！ Never Give Up

搬运于2025-08-24 23:15:44，当前版本为作者最后更新于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)$。