怎么这么唐诗的 DS 都做不出来啊

虽然下蛋爷和红黑树都没做出来。

description

你有一颗有根树，有三种操作：

• 对 \(x\) 子树内深度为 \(k\) 的所有点 \(+s\) 并求出最大值。
• 对 \(x\) 子树内深度 \(\le k\) 的所有点 \(+s\) 并求出最大值。
• 对 \(x\) 子树内所有点 \(+s\) 并求出最大值。

规定：子树内，子树的根节点深度为 \(0\)。

\(1 \le k \le 10\)。

solution

确实自己蛮唐的。

考虑这么一件事情，我对于每个点 \(x\) 维护 \(x\) 子树 \(10\) 层以内所有的按照 BFS 序顺序的值，也就是对于每一层维护一个线段树，发现一个事情，我对于 \(1, 2\) 操作，只会对 \(x\) 的 \(k\) 级祖先的线段树进行更改，这个复杂度大概是 \(O(k^2)\) 的，虽然但是能过去就好了。然后考虑子树 \(+s\) 怎么维护，本质上就是我们打上一个 \(tag\)，表示将所有点的所有线段树都进行更改，只有 \(x\) 的 \(k\) 级祖先不是全部更改，但是发现最大值可能不太好维护，让我想想。

哦本质上我还可以维护一个 DFS 序，再对每个点维护一个子树最大值，对于一个结点的更改信息，我们直接跳祖先即可，时间复杂度是 \(\log^2 n\) 的，相当于我又给祖先打上了一个 \(tag\)，BFS 序维护的是每个点内部的线段树，而 DFS 序维护的是每个点打 \(tag\) 的线段树，发现树链剖分既可以维护链又可以维护子树，相当于两个 \(tag\) 都可以用同一个线段树进行操作。

等等我好像只对祖先做了更改，没对子树内部点做更改。没关系我每次更改可以暴力把 \(x\) 的 \(k\) 级祖先的值对其进行一次 \(tag\) 覆盖，不过有很多细节要考虑。