长链剖分小技巧

· · 个人记录

给定一棵树，有 n 次操作，每次操作形如 x,d,z（保证 d 不超过 x 子树内最大深度），你需要对 x 子树外，距离 x 恰好为 d 的点 y 执行 \text{chkmin}(a_y,z)，求最终的数组 a。

首先对树进行长链剖分。然后考虑直接对树进行 dfs，维护一个数组 f_i 表示已经处理完了子树外的所有操作，此时子树内深度为 i 的点答案是 f_i。

考虑向下递归。首先往重儿子递归是简单的，因为操作的性质，所以每个子树内深度为 len 的轻儿子只有 \mathcal O(len) 种本质不同的操作，暴力处理对 f 的影响即可。

而往轻儿子递归的时候，其余轻儿子对他的贡献也是好算的，只需要记录每个深度中所有轻儿子操作的最小值和次小值。

然后对于重儿子对一个深度为 len 的轻儿子的贡献，显然也只有 len 种贡献，只需要把它找到即可。所以每个点额外维护一个 g_{i} 表示 now 子树内的所有操作对子树外的影响延长出去 i 的最小答案，也就是对于所有 (x,d,z)，d-(dep_x-dep_{now})=i 中 z 的最小值。i 的上界显然也是 now 子树深度，所以这个也是可以长链剖分维护的。

上面的 f 处理了子树外操作的贡献，而 g 也能处理对子树内操作的贡献。复杂度是 \mathcal O(n) 的。