Luogu7124 [Ynoi2008] stcm

题意：本题是构造题。

给定一棵树，你可以维护一个集合 ，支持三种操作：

1. 将 中插入一个节点
2. 撤回上一次插入操作
3. 将 标为第 个点的子树补信息

一个点 的子树补信息定义为，树的点集除去 的子树（包括 ）内的点得到的集合。

需要得到每个点的子树补信息。

1 操作的次数限制为 次。

多组数据， ，，时限 。

---

根据数据范围，最终使用的操作次数应是 级别的。

• 菊花图

等价于构造单独缺每个点的集合。

建立一棵线段树，并遍历。走向左儿子时，将右侧加入集合。走向右儿子时，将左侧加入集合。

这样，走到叶节点时，所得的集合就是缺少该点的集合。

每个数会被加入“线段树上深度”次，于是操作数为 。

• 一般情况

将树轻重链剖分。

对于每条重链，首先 是重链顶的子树补信息，然后一路加入轻子树。

轻边子树大小和是 的。

接下来的问题是如何得到轻儿子的子树补信息。

取出重链上挂着的所有轻子树，问题又转化为类似菊花图的情况。

根据 HLD 的结论，根据轻儿子的大小建哈夫曼树即可让总复杂度为 。