题意:训练指南P192

分析:主要就是一个在路径压缩的过程中,更新点i到根的距离

#include 
     
      using namespace std;const int N = 2e4 + 5;struct DSU	{	int rt[N], d[N];	void init(void)	{		memset (rt, -1, sizeof (rt));		memset (d, 0, sizeof (d));	}	int Find(int x)	{		if (rt[x] != -1)	{			int root = Find (rt[x]);	//先找到根			d[x] += d[rt[x]];			//回溯的过程把距离更新			return rt[x] = root;		//路径压缩		}		else	return x;	}	void Union(int x, int y)	{		if (x == y)	{			d[x] = 0;	return ;		}		else	{			rt[x] = y;			d[x] = abs (x - y) % 1000;		}	}	bool same(int x, int y)	{		return Find (x) == Find (y);	}}dsu;int main(void)	{	int T;	scanf ("%d", &T);	while (T--)	{		int n;	scanf ("%d", &n);		char str[3];	dsu.init ();		int x, y;		while (scanf ("%s", str) == 1)	{			if (str[0] == 'O')	break;			if (str[0] == 'E')	{				scanf ("%d", &x);				dsu.Find (x);				printf ("%d\n", dsu.d[x]);			}			else	{				scanf ("%d%d", &x, &y);				dsu.Union (x, y);			//初始就是到fa的距离			}		}	}	return 0;}