学步园

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=34236#problem/E

题意：给你一个n，分别代表从1~N个堆，每堆初始时都有一个方块（分别按照初始堆编号），现在执行P步操作，只有M和C操作，M x y代表，将x移动到y堆上去，C x代表求第x个方块在现在所在堆中位于它的下面的方块的个数（可以理解为移动时自上向下放方块）；

解析：使用一个数组num存储第i个方块下的方块数，初始时赋值为0（因为开始时都为1，它的下面没有其它方块），然后每次查找时，更新该集合（区间）的值；执行M时（移动），更新单点的值

// e.cpp : 定义控制台应用程序的入口点。
//

//#include "stdafx.h"
#include<iostream>

using namespace std;

const int maxn = 100005;

int fa[ maxn ], num[ maxn ], son[ maxn ];

void Start(){
	for( int i = 0; i < maxn; ++i ){
		fa[ i ] = i;
		num[ i ] = 0;
		son[ i ] = 0;
	}
}

int find( int x ){
	if( fa[ x ] == x )
		return x;
	int temp = find( fa[ x ] );
	num[ x ] += num[ fa[ x ] ];
	return fa[ x ] = temp;
}

void Union( int a, int b ){
	int x = find( a );
	int y = find( b );
	if( x != y ){
		fa[ x ] = y;
		num[ x ] = son[ y ] + 1;
		son[ y ] += son[ x ] + 1;
	}
}

//int _tmain(int argc, _TCHAR* argv[])
int main()
{
	int n, a, b;
	char ch;
	cin >> n;
	Start();
	while( n-- ){
		cin >> ch;
		if( ch == 'M' ){
			cin >> a >> b;
			Union( a, b );
		}
		else{
			cin >> a;
			int temp = find( a );
			cout << num[ a ] << endl;
		}
	}
	return 0;
}