"大新闻！大新闻！jiry_2个逗逼的标程被hack啦"

下午在机房里睡了一觉，醒来的时候一看QQ发现被造了个大新闻...

被hack的原因是标程中的del函数：

void del(){
    if (A[now]) father[A[now]]=A[now];
    now--;
}

其中$A$数组是指第$i$次加边时$father$改变的节点编号，$now$是指当前边的总数。

那么问题就来了..还原之后并查集的$size$发生了变化，但是在标程里头没有还原。

其实我在写标程的时候也想过这个问题...当初因为马上就要比赛了赶进度搞数据标程val啥的，所以也就是粗略的想了一想，觉得如果不去修改它应该也没有什么关系，最大的深度应该也是$O(\log{n})$的，于是就偷懒没有加上这句话了囧。

标程被hack之后仔细想想，也许的确是可以卡到$O(m^{\frac{3}{2}})$。

首先明确方向应该是通过各种操作把并查集维护的森林的深度尽可能增大。如果要把一条链合并到一个点的下方，我们需要这个点的$size$值大于等于这条链。

考虑增大一个点的$size$，于是就有这样的做法：

Add i j
Delete 1

如果$size_i=size_j$，那么我们就用了两次操作把$size_i$加一

那么用上述的方法，如果我们把一个点的$size$增大到$k$，需要的操作次数应为$k(k+1)$次，而且操作完后可以使得当前局面存在$k-1$个点使得它们的$size$值分别等于$0$至$k-1$

那么接下来只需要两两合并就可以得到一条长度为$k+1$的链了。

所以最后我们可以使得并查集的深度达到$O(\sqrt m)$，然后就可以hack掉标程了。

Orz @Picks

如果我们稍微修改一下del函数，就可以过掉这样的数据了：

void del(){
    if (A[now]){
        father[A[now]]=A[now];
        if (B[now]) size[B[now]]--;
    }
    now--;
}

其中$B$数组表示插入第$i$条边时$size$发生变化的点的编号。

很抱歉在给UOJ第一场正式比赛出的题中出了这种错误。下午因为这个被策爷D了很久，心态也有点不对，现在想想的确错在我身上。在这儿对花时间筹备、参加了UOJ Easy Round#1的各位说声对不起。

希望以后不会再发生这种事情。

希望UOJ可以越做越好。

P.S. 有了这个hack功能让人以后如何愉快地出题T^T...