题意:训练指南P246
分析:主要是第二种操作难办,并查集如何支持删除操作?很巧妙的方法:将并查集树上p的影响消除,即在祖先上(sz--, sum -= p),然后为p换上马甲:id[p] = ++pos(可多次),这样id[p]就相当于是新的一个点,那么在Find(x)寻找祖先时要用x的马甲来寻找,即Find (id[x])。
#includeusing namespace std;const int N = 2e5 + 5;int rt[N], sz[N], sum[N], id[N/2];int n, m;void init() { memset (rt, -1, sizeof (rt)); for (int i=1; i