P10147 题解 (2)

口胡一下，感谢 @chenxinyang2006 的指导。

本题事实上存在 1log 做法。考虑类似 天动万象 的，我们可以知道先先扫描 $t$，把树随便剖一下，每次进行 $O(叶子数)$ 个单点修改和 $O(叶子数)$ 个链向上 shift 即可维护出全部信息，考虑把所有还剩下 $\neq 1$ 个儿子的节点建出虚树并维护出链信息和，那么查询可以被拆成 $1$ 次虚树上链查询信息， $O(1)$ 次平衡树上查询和 $O(1)$ 次已删除节点信息查询。显然，每一轮在 $O(叶子数)$ 个操作后会删去所有叶子，所以总时间复杂度是 $O((n+q)\log n)$ 的，空间是线性的。

代码太难写，咕了。