[Luogu 1196] NOI2002 银河英雄传说

<题目链接>

---

话说十六年前的 NOI 真简单。。。

我一开始还把题看错了…

题意：一群人，每个人各自成一队，每次命令让两队首位相接合成一队，每次询问问你某两个人之间有几个人。

容易想到合并用并查集来实现。

至于计数，\(\mathrm{sum}_i\) 表示 \(i\) 到队首有几个人（如果 \(i\) 在队首，\(\mathrm{sum}_i = 0\)）；

\(\mathrm{num}_i\) 表示以 \(i\) 为队首的队伍有几个人（如果 \(i\) 不在队首， \(\mathrm{num}_i = 0\) ）。

并查集 Find 的时候，递归回溯时更新 \(\mathrm{sum}_i\)，不断加上其父亲的 \(\mathrm{sum}\)。

合并的时候，首先建立父子关系，然后更新 \(\mathrm{num}\) 和 \(\mathrm{sum}\)，具体见代码中的 Merge 函数。

询问的话，如果两个人在同一队列中，两人的距离为他们到队首的距离差减一，即 \(|\mathrm{sum}_x - \mathrm{sum}_y| - 1\)。

完结撒花，还是挺好写的 qwq

---

#include <cstdio>

#include <cstdlib>

const int MAXN=30010;

int n;

class UFS

{

	private:

		int f[MAXN],sum[MAXN],num[MAXN];

		int Find(int x)

		{

			if(x==f[x])

				return x;

			int t=Find(f[x]);

			sum[x]+=sum[f[x]];

			return f[x]=t;

		}

	public:

		UFS(void)

		{

			for(int i=1;i<=30000;++i)

			{

				f[i]=i;

				sum[i]=0;

				num[i]=1;

			}

		}

		void Union(int x,int y)

		{

			int a=Find(x),b=Find(y);

			f[a]=b;

			sum[a]+=num[b];

			num[b]+=num[a];

			num[a]=0;

		}

		void Query(int x,int y)

		{

			if(Find(x)^Find(y))

				puts("-1");

			else

				printf("%d\n",abs(sum[x]-sum[y])-1);

		}

}S;

int main(int argc,char** argv)

{

	scanf("%d",&n);

	for(int x,y;n--;)

	{

		char opt;

		scanf("\n%c %d %d",&opt,&x,&y);

		if(opt=='M')

			S.Union(x,y);

		else

			S.Query(x,y);

	}

	return 0;

}