Cube Stacking POJ - 1988 （带权并查集）

Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
* In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
* In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.

Write a program that can verify the results of the game.

Input

* Line 1: A single integer, P

* Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a 'M' for a move operation or a 'C' for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.

Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.

Output

Print the output from each of the count operations in the same order as the input file.

Sample Input

Sample Output

1
0
2

有两种操作：

一种是把包含x的堆栈里的所有元素按顺序放在包含y的元素的栈顶

一种是输出包含x的堆栈里的在x下面的元素的个数

由于询问次数很多，直接模拟会超时

所以加了一个deep数组

存的是儿子节点到父节点的距离

然后输出的时候就用父节点的sum-deep-1就行了

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn=1e5+5;
#define ll long long
int f[maxn],deep[maxn],sum[maxn];
int getf(int x)
{
    if(x==f[x])
        return x;
    int temp=f[x];
    f[x]=getf(temp);
    deep[x]+=deep[temp];
    return f[x];
}
void merg1e(int x,int y)
{
    int t1=getf(x);
    int t2=getf(y);
    if(t1!=t2)
    {
        f[t2]=t1;
        deep[t2]=sum[t1];
        sum[t1]+=sum[t2];
    }
}
void init()
{
    for(int i=0;i<=30000;i++)
    {
        sum[i]=1;
        f[i]=i;
        deep[i]=0;
    }
}
int main()
{
    int q;
    init();
    scanf("%d",&q);
    while(q--)
    {
        char op[2];
        scanf("%s",op);
        if(op[0]=='M')
        {
            int x,y;
            scanf("%d%d",&x,&y);
            merg1e(x,y);
        }
        else
        {
            int x;
            scanf("%d",&x);
            printf("%d\n",sum[getf(x)]-1-deep[x]);
        } 
    }
    return 0;
}