自动搬运

查看原文

来自洛谷，原作者为

	2huk Where should my destinaion be at? 我问我自己。

搬运于2025-08-24 22:11:11，当前版本为作者最后更新于2024-04-18 13:40:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 给定一颗 $n$ 个节点的树。有 $m$ 个骑士，最开始第 $i$ 个骑士在 $p_i$ 节点上，武力值为 $f_i$。接下来有 $q$ 次操作 $(t_i, x_i, y_i)$：
  • $t_i = 1$，输出树上 $x_i, y_i$ 路径上的前 $k$ 大骑士的武力值。
  • $t_i = 2$，$p_{x_i} \gets y_i$；
  • $t_i = 3$，$f_{x_i} \gets y_i$。
• $n, m \le 4 \times 10^4$，$q \le 8 \times 10^4$，$\color{red}k \le 20$。

显然需要树链剖分，将树上问题转化成序列上问题。

发现 $k$ 很小，所以我们可以用线段树维护前 $k$ 大，并用 $\mathcal O(k)$ 的时间复杂度 pushup。

注意可用 multiset 存储每个叶子节点上的骑士编号和骑士武力值。