算是挺基础的东西
Description
约翰和贝茜在玩一个方块游戏．编号为1到n的n(1≤n≤30000)个方块正放在地上．每个构成一个立方柱．
游戏开始后，约翰会给贝茜发出P(1≤P≤100000)个指令．指令有两种：
1．移动(M)：将包含X的立方柱移动到包含Y的立方柱上．
2．统计(C):统计名含X的立方柱中，在X下方的方块数目．
写个程序帮贝茜完成游戏．
Input
第1行输入P，之后P行每行输入一条指令．形式为“M X Y”或者“C X”
输入保证不会有将立方柱放在自己头上的指令．
Output
每一行，对于每个统计指令，输出其结果．
Sample Input
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output
1
0
2
0
2
题目分析
带权并查集的模板题。
之所以能够用并查集做，是因为：即便集合内每一个元素不是完全等价的，但它满足能够独立带权的性质。
嗯……如果是初学带权并查集的话还是无视上面那句话好了。学的时候还是靠代码理解，理解之后自然就会有自己对于一块方面的总结了。
对于每一个维护$dis[i]$和$sum[i]$，其中$dis[i]$表示它下面有几个方块；$sum[i]$表示它这摞方块一共有几个。维护两个量是为了方便合并时的转移。
因为这题有上下之分，所以合并过程是既不能随便合并（破坏顺序）；也难以按秩合并（麻烦）。路径压缩看上去好像也不行，然而实际上可以这样操作：保留逻辑上的上下顺序（换句话说，就是我们在考虑问题时候当做它是上下有序），但是操作时就路径压缩（运行结果上来看，元素之间路径被压缩了，因此并没有上下顺序）。
这样便发现，合并时候把整摞方块的最下面方块作为根是更方便的。
#include<cstdio>
#include<cctype>
const int maxn = ; int fa[maxn],sum[maxn],dis[maxn];
int q; int get(int x)
{
if (fa[x]!=x){
int tt = fa[x];
fa[x] = get(fa[x]);
dis[x] += dis[tt];
}
return fa[x];
}
void unions(int x, int y)
{
fa[x] = y;
dis[x] += sum[y];
sum[y] += sum[x];
}
int main()
{
scanf("%d",&q);
for (int i=; i<=; i++) fa[i] = i, sum[i] = ;
for (int i=; i<=q; i++)
{
char ch = getchar();
while (!isalpha(ch)) ch = getchar();
int x,y;
if (ch=='M'){
scanf("%d%d",&x,&y);
int fx = get(x), fy = get(y);
if (fx!=fy) unions(fx, fy);
}else{
scanf("%d",&x);
get(x);
printf("%d\n",dis[x]);
}
}
return ;
}
END