ARC170F Edge Deletion 2

某人竟然忘记了星期天晚上有 \(\text{ARC}\)，我不说是谁。

首先选择最小点删除和最小字典序都是最小化，所以可以弱化最小点删除的限制，现在原问题就变成了可以删除任意一个点的出边，如果没有出边则为 \(0\)(这个其实本题中是最优的策略)。

如果每一个点向其删除的出边连边，先考虑它会形成什么样的一个形态，可以发现这个树被划分成了若干个子连通块，每个连通块都是一个内向树，且根节点刚好就是 \(0\) 的点。但要求根节点的编号要比其出边所有节点大且其所有出边都要连向它，否则无法在操作这个点时使其成为孤立点。

接下来就比较麻烦了，但可以发现根据这个结构，所有出边相同的可以将其分配至一个等价类，那么我们显然是按照等价类的最小值从小到大分配标号。同样的，如果我们从小到大贪心，每次将一个点尽量的归并至一个标号较小的等价类但同时满足合法性，则一定最优。

现在可以分析每个等价类的合法条件，如果一个等价类的大小 \(\geqslant 2\)，则其直径中点一定是它们连向的点，而当等价类的大小 \(=1\) 时，其连向的点可以是任意的，但决不可以不存在。那么若当前考虑的节点为 \(i\)，如果 \(i\) 满足其出边所有节点大且其所有出边都连向它或还没有确定连接方式，则 \(i\) 可以作为根取到 \(0\)，否则 \(i\) 应当与最小的等价类进行合法的合并。如果当前考虑的等价类大小 \(\geqslant 2\)，则当前等价类的出边节点 \(x\) 是固定的，所以只要不存在 \(x\) 到 \(i\) 的边即可(因为 \(x\) 到 \(i\) 与 \(i\) 到 \(x\) 不能同时存在)，如果当前考虑的等价类大小为 \(1\)，令其为 \(d\)，那么这样如果 \(d\) 与 \(i\) 合并，则 \(d\) 与 \(i\) 的中点 \(x\) 则成为了新的出边点，此时则要求 \(x\) 到 \(d,i\) 的边都不能存在。如果上述条件均不满足，则不得不新开一个等价类。

但这样一交发现只过了三个点，注意到上述过程忽视了一个东西，在等价类的大小 \(=1\) 时该点的出边集合如果唯一，则它是被定住的不能修改，此外，我们也不能让等价类的大小 \(=1\) 时该点没有合法的出边。但实际上只有加边时会导致一个等价类的大小 \(=1\) 的出边集合大小进行改变，且每次只会减少 \(1\) 或 \(2\)(即分别对应上述添加 \(i,x\) 与添加 \(d,i\) 与 \(x\) 的情况)，如果在减少后发现一个点的出边集合的大小为 \(1\)，则立刻将这个点的出边连向唯一的一个出边集合内的点，而且当出边集合大小为 \(2\) 时我们还不能执行 \(d,i\) 向 \(x\) 的连边，因为这样会使出边集合减至 \(0\)。

上述过程只需要查询一个点的出边信息最小值与修改一个点的出边信息，可以用 \(\text{set}\) 维护做到 \(O(n \log n)\)。