题解 | #叠积木#

using namespace std;
const int N = 30010;
int d[N];//代表当前节点到其祖宗节点的长度
int c[N];//当c[n](n==祖宗节点)c[n]表示当前列的大小
int fa[N];//用于并查集记录父亲节点
int find(int a)
{
	if (fa[a] == a) return a;
	else {
		int t = find(fa[a]);
		d[a] += d[fa[a]];//返回时一直更新
		return fa[a]=t;//找到祖父节点一路返回,并同时进行路径压缩使得下一次访问一节点不会再对a到原祖父节点之间的dis进行重新增加，而是一步到原祖宗节点
	}
}
void un(int a, int b)
{
	int gfa = find(a);
	int gfb = find(b);//find函数更新dis（在a的祖宗节点跟新时更新，否则会一步到祖宗节点并+=0，相当于不变）
	fa[gfa] = gfb;
	d[gfa] += c[gfb];
	c[gfb] += c[gfa];
}
int main()
{
	int m;
	cin >> m;
	for (int i = 1; i <=N; i++)
	{
		fa[i] = i;
		c[i] = 1;
		d[i] = 0;
	}
	char op;
	int a, b;
	while (m--)
	{
		cin >> op;
		if (op == 'M')
		{
			cin >> a >> b;
			un(a,b);
		}
		else
		{
			cin >> a;
			find(a);//由于进行了路径压缩，且a再祖父节点改变时不一定会被访问，所以为了确保dis[a]正确性，应该调用一次find函数
			cout << d[a]<<endl;
		}
	}