题意:训练指南P192
分析:主要就是一个在路径压缩的过程中,更新点i到根的距离
#include <bits/stdc++.h>
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;
}