记录编号	53214	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.650 s
提交时间	2013-02-22 17:53:39	内存使用	0.66 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<cstring>
using namespace std;
//注意:数组下标是1~n
const int SIZEN=30000;
int father[SIZEN+1]={0};//就是father
int deep[SIZEN+1]={0},behind[SIZEN+1]={0};//每个点深度和后面点的个数
void initialization(void){
	int i;
	memset(deep,0,sizeof(deep));
	for(i=1;i<=SIZEN;i++) father[i]=i,behind[i]=1;
}
int getfather(int x){//找到x的最远祖先,把x的路径信息记录在deep上,然后把x连到那个最远祖先上
	if(father[x]==x) return x;
	int p=getfather(father[x]);
	deep[x]+=deep[father[x]];
	father[x]=p;
	return father[x];
}
void work(void){
	int t;
	scanf("%d",&t);
	int i,a,b;
	char ch;
	for(i=1;i<=t;i++){
		/*for(int km=1;km<=20;km++) cout<<deep[km]<<" ";
		cout<<endl;*/
		scanf("%c%c",&ch,&ch);//这个好奇葩的赶脚......
		if(ch=='M'){
			scanf("%d%d",&a,&b);
			father[a]=getfather(a),father[b]=getfather(b);
			deep[father[a]]+=behind[father[b]];
			behind[father[b]]+=behind[father[a]];
			father[father[a]]=father[b];
		}
		else{
			scanf("%d%d",&a,&b);
			if(a==b){
				printf("0\n");
				continue;
			}
			else{
				father[a]=getfather(a),father[b]=getfather(b);
				if(father[a]!=father[b]) printf("-1\n");
				else printf("%d\n",(int)abs((deep[a]-deep[b])*1.0)-1);
			}
		}
	}
}
int main(){
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	initialization();
	work();
	return 0;
}