前置知识点：并查集，不会的请先做模板

首先很容易看出这是一道与并查集有关的题目，但由于他需要维护在x下面的方块个数，所以和并查集又不完全一样。

你会发现他只是比普通的并查集需要多维护一个权值而已，而这种并查集就是——带权并查集

按照并查集的思路，我们需要研究以下几个问题：

1.维护哪些权值

2.如何合并

3.如何查询

4.如何路径压缩

$1^o$ 需要维护哪些权值

这里有一个小技巧，由于我们需要维护的权值只有在$x$下面的数量，所以我们可以让一堆中的最下面的一个为当前集合的根，方便以后操作。

我们需要维护一下三个值：

struct node{
	int fa,up,down;//分别是当前集合的根，在他上面的方块数(包括自己），在他下面的方块数
}father[100005];

$2^o$ 如何合并

当我们要把$x$，$y$（$x$,$y$均为集合的根）两个集合合并时会产生三种变化。

1.$x$集合的每个数的$down$都会加上$y$集合中的所有元素。

而$y$集合中的所有元素会存在$father[y].up$中

所以每次: $father[x].down=father[y].up$即可

2.$y$集合中的每个数的$up$都会加上$x$集合中的所有元素。

而$x$集合中的所有元素都会存在$father[x].up$中

所以每次：$father[y].up+=father[x].up$即可

3.并查集常规祖先变换 每次：$father[x].fa=father[y].fa$即可

给出片段代码（f1相当于x，f2相当于y)

inline void unnion(int f1,int f2)
{
	father[f1].fa=f2;//更新fa
	father[f1].down=father[f2].up;//更新down
	father[f2].up+=father[f1].up;//更新up
}

$3^o$ 如何查询

查询比较简单，只要对于$x$输出$father[x].down$即可。

$4^o$ 如何路径压缩

我们知道在寻找一个集合的根时，路径压缩是一个很重要的优化。

而到了带权并查集中，路径压缩显得更为重要。

例如本题我们每次更新权值，都只更新了每个集合的根，而显然同一个集合中的每一个点权值是不一样的，所以此时我们就要在路径压缩时把权值传下去。（有点类似于线段树的push_down下传）

我们可以稍微画个图分析一下，首先对于每个点我们显然只有$down$这个权值还没有维护好，所以只需维护$down$

而且不难发现，对于每个点，所缺少的都是上次合并时更新到根节点中的$father[y].up$。

又由于我们的更新方式是这样的$father[x].down=father[y].up$。

所以我们只需要在路径压缩的过程中将每个点的$down$都加上根节点的$down$就行了。

放部分代码：

inline int Find(int x)
{
	if (father[x].fa!=x)
	   {
	   int gr=Find(father[x].fa);//找根，顺便更新到他的父亲中
	   father[x].down+=father[father[x].fa].down;//路径压缩，下传权值
	   return father[x].fa=gr;
	   }
	return father[x].fa;
}

这样维护下来就可以解决了~~~

放AC代码：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0;
	char c=getchar();
	bool f=0;
	while (!isdigit(c))
		  f|=(c=='-'),c=getchar();
	while (isdigit(c))
		  x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}
int p;
struct node{
	int fa,up,down;
}father[100005];
int ans[100005];
inline int Find(int x)//找根，顺便下传权值
{
	if (father[x].fa!=x)
	   {
	   int gr=Find(father[x].fa);
	   father[x].down+=father[father[x].fa].down;
	   return father[x].fa=gr;
	   }
	return father[x].fa;
}
inline void unnion(int f1,int f2)//合并
{
	father[f1].fa=f2;
	father[f1].down=father[f2].up;
	father[f2].up+=father[f1].up;
}
int main(){
	for (register int i=1;i<=100005;++i)
	    father[i].fa=i,father[i].up=1,father[i].down=0;
	p=read();
	for (register int i=1;i<=p;++i)
		{
		char c=getchar();
		while (!isalpha(c))
		      c=getchar();
		if (c=='M')
		   {
		   int x=read(),y=read();
		   int f1=Find(x),f2=Find(y);
		   if (f1!=f2)
		      unnion(f1,f2);
		   }
		else
		   {
		   int x=read();
		   Find(x);//在查询前要把权值下传
		   printf("%d\n",father[x].down);
		   }
		}
	return 0;
}

最后送个福利给看到最后的$Oier$们