题意：
如果是Ｉｕｖ则是把ｕ的父节点设置为ｖ；并且ｕ到ｖ的距离为｜ｕ－ｖ｜ ％ １０００；
如果Ｅｕ 则输出ｕ到根的距离；
Ｏ结束；
?
思路：
在合并阶段就是普通的并查集，但还需要算一个距离：
但每次查询时，就应该把距离累加起来，并记录下来：
?
ＡＣ代码：
?
#include#include #include using namespace std; const int N = 20000 + 5; int p[N]; int dis[N]; int n; void init(int n) { for(int i = 0; i <= n; i++) { p[i] = i; dis[i] = 0; } return ; } int find_parent(int x) { if(x != p[x]) { int r = find_parent(p[x]); dis[x] += dis[p[x]]; return p[x] = r; } return x; } void Union(int u, int v) { p[u] = v; dis[u] = abs(u - v); dis[u] %= 1000; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); init(n); char c; while(1) { getchar(); c = getchar(); if(c == 'I') { int a,b; scanf("%d%d",&a,&b); Union(a,b); } else if(c == 'E') { int a; scanf("%d",&a); find_parent(a); printf("%d\n",dis[a]); } else break; } } }
?