poj 1988(集計)

标题:m回の操作を行い、M x yはxを含む集合をyの上、C xに移動し、xの下にいくつかの要素を計算する.
問題を解く構想:この問題は使いやすくて、集を調べることができますが、ここは少し回ります.最初に思いついたのは、x以下のノード数を表すnum[x]を作成することですが、num[x]を更新するには、どのノードの親ノードがpであるかを列挙しなければなりません.ノード数が多すぎるため、TLEは避けられません...
ここでは、x以下のノード数を計算するときに、xが存在する集合要素の個数-その上の個数-それ自体を使用することができます.これで列挙を避けることができます.
AC:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 30005;
int fa[maxn],cnt[maxn],top[maxn];

int find(int x)
{
	if(fa[x] == x) return x;
	int t = fa[x];
	fa[x] = find(fa[x]);
	top[x] += top[t];
	return fa[x];
}

void Union(int x,int y)
{
	int fx = find(x);
	int fy = find(y);
	if(fx != fy)
	{
		fa[fy] = fx;
		top[fy] = cnt[fx];
		cnt[fx] += cnt[fy];
	}
}

int main()
{
	int p,a,b;
	char ch;
	for(int i = 1; i < maxn; i++)
	{
		fa[i] = i;
		top[i] = 0;
		cnt[i] = 1;
	}
	scanf("%d",&p);
	while(p--)
	{
		getchar();
		ch = getchar();
		if(ch == 'M')
		{
			scanf("%d%d",&a,&b);
			Union(a,b);
		}
		else 
		{
			scanf("%d",&a);
			int f = find(a);
			printf("%d
",cnt[f] - top[a] - 1);
		}
	}
	return 0;
}