题解：P5478 [BJOI2015] 骑士的旅行

2huk · 2024-04-18 13:40:15 · 题解

• 给定一颗 n 个节点的树。有 m 个骑士，最开始第 i 个骑士在 p_i 节点上，武力值为 f_i。接下来有 q 次操作 (t_i, x_i, y_i)：

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

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

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