记录编号	557764	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.490 s
提交时间	2020-11-25 21:47:37	内存使用	10.25 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxN = 3e5 + 10;

void merge(int x, int y);
int get(int x);

int T;
int f[maxN], d[maxN], sz[maxN];
int main(void){
	freopen("galaxy.in", "r", stdin);
	freopen("galaxy.out", "w", stdout);
	scanf("%d", &T);
	for (int i = 1; i < maxN - 10; i ++){
		f[i] = i;
		sz[i] = 1;
	}
	for (int i = 1; i <= T; i ++){
		char opt[2];
		int x, y;
		scanf("%s%d%d", opt, &x, &y);
		if (opt[0] == 'C'){
			int fx = get(x), fy = get(y);
			if (fx == fy)
				printf("%d\n", abs(d[x] - d[y]) - 1);
			else
				puts("-1");
		}
		else{
			merge(x, y);
		}
	}
	return 0;
}

void merge(int x, int y){
	x = get(x), y = get(y);
	f[x] = y, d[x] = sz[y];
	sz[y] += sz[x];
}

int get(int x){
	if (x == f[x])
		return x;
	int root = get(f[x]);
	d[x] += d[f[x]];
	return f[x] = root;
}