[NOI2002]银河英雄传说，洛谷之提高历练地，并查集

正题

      第四题：[NOI2002]银河英雄传说

      这道题看上去很简单，做起来却对ij之间飞船的数量给搞混了。那么我们很容易就可以知道，要求ij之间的飞船个数，只要我们知道j前面有多少飞船，i前面有多少飞船即可，直接用abs(d[i]-d[j])-1即可。

      恶心就恶心在维护d值上。

      首先我们要讨论初始化，用d来记录i前面有多少个飞船，初始值设为0，that[i]来存储以i开头的队列的长度，如果i不是队头，那么就为0.很明显初始值要设为1.

      在转移的过程中，加到后面的队列的d当然要加上前面队列的长度（给队头的加上即可，后面的会根据当前祖先来更新）。后面的that当然要变为0.

      讲讲怎么维护这个d和fa。d在fa的d更新完毕后要更新自己的，fa要等到d更新完再更新。否则就会出错，看图

代码<虽然有代码帮助理解但是自己实现会更好>

#include
#include
#include
#include
using namespace std;

int T;
const int n=30000;
int d[30010];
int f[30010];
int that[30010];

int findpa(int x){
	if(f[x]!=x){
		int now=findpa(f[x]);
		d[x]+=d[f[x]];
		f[x]=now;
	}
	return f[x];
}

int main(){
	scanf("%d",&T);	
	for(int i=1;i<=n;i++)
		d[i]=0,f[i]=i,that[i]=1;
	char c[2];
	int x,y;
	for(int i=1;i<=T;i++){
		scanf("%s",c);
		scanf("%d %d",&x,&y);
		int fx=findpa(x),fy=findpa(y);
		if(c[0]=='M'){
			d[fx]+=that[fy];
			f[fx]=fy;
			that[fy]+=that[fx];
			that[fx]=0;
		}
		else{
			if(fx!=fy) printf("-1\n");
			else{
				printf("%d\n",abs(d[x]-d[y])-1);
			}
		}
	}
}