题解：P10574 [JRKSJ R8] 暴风雪

这我哪会啊。。。

感觉比大多数根号题要优美太多了。

考虑到 $w\ge 1$，直接从下往上跳给每个点的权值 ckmax 即可。一个观察是 ckmax 的权值只有 $O(\sqrt n)$ 段（这是因为 $x$ 的祖先中，只有 $O(\sqrt n)$ 个点存在不包含 $x$ 的子树中有深度与 $x$ 相等的点），考虑对着这个做。

先考虑如何求分段。这相当于每次找到最浅的祖先，使得其存在一个不包含 $x$ 的子树中有深度为 $x$ 的点。考虑长剖，显然跳轻边时这一定是答案，否则这相当于找一条长链向上的第一个 $\ge x$ 的数。考虑对每个 $x$ 开一个 vector 维护所有轻子树深度大于等于 $d_x$ 的点，显然 vector 内不会加入超过轻子树 siz 个点，于是复杂度是 $O(n)$ 的，查询直接在对应的 vector 上从上往下不断跳直到不是 $x$ 的祖先即可。这样即可 $O(n)$ 预处理 $O(\sqrt n)$ 求分段。维护每个节点每一层权值的事情在长剖过程中顺便做即可。

然后考虑怎么做 ckmax。考虑这样一个事情：记 $a_{1\sim k}$ 为从上往下 ckmax 的区间长度，由 $a_i$ 的意义有 $\sum i\times a_i\le n$，我们有 $\sum_i\log(a_i+1)=O(\sqrt n)$。贺一个 hos_lyric 的 simple proof：