题解笔记

P1196 银河英雄传说
带权并查集（根搭积木很像）：

对于每个点，分别记录所属链的头结点、该点到头结点的距离以及它所在集合的大小。

每次合并将y接在x的尾部，改变y头的权值和所属链的头结点，同时改变x的尾节点。

注意：每次查找的时候也要维护每个节点的权值。

每次查询时计算两点的权值差。

代码(含模板)：

#include <bits/stdc++.h>
#define int ll
using namespace std;

using ll = long long;

#define R(i, a, b) for (int i = (a); i <= (b); ++i)
#define P(i, a, b) for (int i = (b); i >= (a); --i)
#define F(v, ...) for (auto __VA_ARGS__ : v)
#define lb(a) for (; a; a -= (a & -a))
#define lc(x, a) for (; x <= a; x += (x & -x))

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) putchar(x)
inline int read() {
    int x = 0, sgn = 0; char s = getc();
    while(!isdigit(s)) sgn |= s == '-', s = getc();
    while(isdigit(s)) x = x * 10 + s - '0', s = getc();
    return sgn ? -x : x;
}
inline void print(int x) { if(x >= 10) print(x / 10); putc(x % 10 + '0'); }

bool Mbe;
int t;
int cnt[30007],fa[30007],dis[30007];

int findd(int x){
	if(fa[x]==x)return x;
	int k=fa[x];
	fa[x]=findd(fa[x]);
	dis[x]+=dis[k];
	
	cnt[x]=cnt[fa[x]];
	return fa[x];
//	return fa[x]==x?x:fa[x]=findd(fa[x]);
}
void unionn(int x,int y){
	//union x to y
//	cnt[y]+=cnt[x];
//	cnt[x]=0;
	int dx=findd(x),dy=findd(y);
	fa[dx]=dy;
	dis[dx]+=cnt[dy];
	cnt[dy]+=cnt[dx];
	cnt[dx]=cnt[dy];
}

bool Med;

signed main() {
	for(int i=1;i<=30004;++i)fa[i]=i;
	for(int i=1;i<=30002;++i)cnt[i]=1;
	for(int i=1;i<=30002;++i)dis[i]=0;
	scanf("%lld",&t);
	while(t--){
		int x,y;
		char ch;
		cin>>ch;
		scanf("%lld%lld",&x,&y);
		if(ch=='M'){
			unionn(x,y);
		}
		else{
			if(findd(x)==findd(y)){
				cout<<abs(dis[x]-dis[y])-1<<endl;
			}
			else cout<<-1<<endl;
		}
	}
	
	fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
	return 0;
}