http://uoj.ac/problem/14

题解很好的~

不带路径压缩的并查集能保留树的原本形态。

按秩合并并查集可以不用路径压缩，但是因为此题要删除，如果把深度当为秩的话不好更新秩的值，所以把子树大小当为秩。

合并直接合并，删除直接删除，每条边只会被添加进树一次，至多被删除一次。

离线特殊考虑一下return的情况就可以了QwQ

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 300003;

const int M = 500003;

int in() {

	int k = 0; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar());

	for(; c >= '0' && c <= '9'; c = getchar())

		k = k * 10 + c - 48;

	return k;

}

int fa[N], sz[N], q[M], tail = 0, intree[M], n, m, cnt = 0;

ll ans[M], treesum = 0;

int find(int x) {return fa[x] == x ? x : find(fa[x]);}

void merge(int x, int y, int len) {

	x = find(x); y = find(y);

	q[++tail] = len;

	if (x == y)

		intree[len] = -1;

	else {

		++cnt;

		treesum += (ll) len;

		if (sz[x] > sz[y]) swap(x, y);

		intree[len] = x;

		fa[x] = y;

		sz[y] += sz[x];

		while (fa[y] != y) {

			y = fa[y];

			sz[y] += sz[x];

		}

	}

}

void del() {

	int x = q[tail--];

	if (intree[x] == -1) return;

	--cnt;

	treesum -= x;

	x = intree[x];

	int y = fa[x];

	sz[y] -= sz[x];

	while (fa[y] != y) {

		y = fa[y];

		sz[y] -= sz[x];

	}

	fa[x] = x;

}

char c[20];

struct node {

	char op;

	int x, y;

} Q[M];

int main() {

	n = in(); m = in();

	for(int i = 1; i <= m; ++i) {

		scanf("%s", c);

		if ((Q[i].op = c[0]) == 'R') continue;

		Q[i].x = in();

		if (c[0] == 'A')

			Q[i].y = in();

	}

	for(int i = 1; i <= n; ++i)

		fa[i] = i, sz[i] = 1;

	for(int i = 1; i <= m; ++i) {

		switch (Q[i].op) {

			case 'A':

				merge(Q[i].x, Q[i].y, i);

				printf("%lld\n", ans[tail] = cnt < n - 1 ? 0 : treesum);

			break;

			case 'D':

				if (Q[i + 1].op == 'R') {

					printf("%lld\n", ans[tail - Q[i].x]);

					printf("%lld\n", ans[tail]);

				} else {

					for(int j = 1; j <= Q[i].x; ++j)

						del();

					printf("%lld\n", ans[tail]);

				}

			break;

			case 'R':

				if (Q[i - 1].op == 'A') {

					del();

					printf("%lld\n", ans[tail]);

				}

			break;

		}

	}

	return 0;

}