在我的个人博客中阅读

题目链接

题目大意

给出一棵 $n$ 个点的树，需要你构建一个操作序列使得树上每一个结点均被标记一次，操作序列由下面三种操作构成：

1. +x： 向当前集合中插入 $x$ 号点。
2. -： 撤销上一次插入操作。
3. =x： 确定当前集合为 $x$ 号点的子树补集并标记 $x$。

$x$ 号点子树补集的定义为 $x$ 号点子树构成的点集在整棵树点集中的补集。

题意可能较难理解，也不是非常容易以较简单的方式字面描述，如果你还是不理解可以手推一下样例。

每个测试点有 $T$ 组测试数据。

$n \le 10^5,~T \le 3,$ +x 操作数量 $\le 4.5 \times 10^6$

分析

观察限制的 +x 操作数量大约在 $O(n \log n)$ 级别，容易想到对树进行重链剖分，然后依次处理每一条重链。

我们发现如果当前集合为 $p$ 点的子树补集且 $p$ 为其所在重链的顶端，我们可以用 $O(siz[p])$ 的操作标记 $p$ 所在重链上的所有点：假设 $p$ 重链上的点从上到下为 $x_1,~x_2,~x_3,\dots$，我们可以先标记 $x_1$，然后将 $x_1$ 和 $x_1$ 的所有轻儿子为根的子树加入集合，然后标记 $x_2$，再将 $x_2$ 和 $x_2$ 的所有轻儿子为根的子树加入集合，以此类推，最终可以 $O(siz[p])$ 标记该重链上的所有点。全局花在该操作上的次数为 $O(n \log n)$ 级别，证明类似 dsu on tree。

我们现在已经可以处理一条重链上的信息了，接下来我们要考虑如何完成重链间的切换。为完成重链间的切换，我们显然是枚举 $p$ 所在重链的所有节点的所有轻儿子，然后考虑将当前集合变为该轻儿子的子树补集然后递归处理该轻儿子所在重链信息。考虑如何在较小的操作步数中将所有轻儿子的子树补集都构造一次。

考虑极端情况，即整棵树为一个菊花图的情况，考虑如何构造方案。稍微尝试一些方法后会发现最优策略为你构造一个类似线段树的结构，然后你从线段树根开始遍历这个线段树：

1. 如果当前节点为叶子节点，标记该节点并跳过下面的步骤并回溯。
2. 将当前节点右儿子对应区间内的所有节点加入集合。
3. 递归处理左儿子。
4. 撤销 2 步骤中的插入操作。
5. 将当前节点左二子对应区间内的所有节点加入集合。
6. 递归处理右儿子。
7. 撤销 5 步骤中的插入操作。

容易发现该方法可以用 $O(n \log n)$ 此操作标记所有的点，因为每一个点一共被操作的次数等于其祖先数量。

我们同样可以使用该方法处理我们的轻儿子的问题。我们可以先将重链上的所有节点加入集合，然后将每个轻儿子视为一个点，对所有的轻儿子构建一棵线段树，然后在线段树上从根开始递归处理，到叶子结点时将原本的“标记该结点”换为“递归处理该节点所在的重链”。

但是容易发现这样的方法并不能保证操作次数复杂度一定正确，因为修改每一个轻儿子的花费是 $siz[\text{轻儿子}]$ 而不是 $1$。考虑这棵线段树上的总操作数是等于 $\sum_{i \in \text{叶子节点}} siz[i] \times dep[i]$，我们想要最小化它的值。这时我们发现哈夫曼树正好就是在最小化这个值，所以我们将“构造线段树”换为“构造哈夫曼树”就可以使该操作复杂度成为 $O(siz[p] \log siz[p])$，递归方法不变。与处理重链时的复杂度证明相似，可以发现全局花在这一操作上的总操作次数为 $O(n \log n)$。

总操作次数 $O(n \log n)$。

代码

View on Github