45 lines
1.5 KiB
C++
45 lines
1.5 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 20010;
|
||
int fa[N];
|
||
int d[N]; // d[i] 表示距离根节点的距离
|
||
int n;
|
||
|
||
//带权并查集模板
|
||
int find(int x) {
|
||
//点权的理解：每个点到根的距离
|
||
if (fa[x] == x) return x; //自己是老大，返回自己
|
||
int root = find(fa[x]); //通过自己父亲找老大
|
||
d[x] += d[fa[x]]; //点权在路径压缩过程中，需要加上父亲的点权
|
||
return fa[x] = root; //路径压缩
|
||
}
|
||
|
||
int main() {
|
||
int T;
|
||
cin >> T;
|
||
while (T--) {
|
||
cin >> n;
|
||
// 带权并查集初始化
|
||
// 1、自已是自己的祖先
|
||
// 2、自己距离自己的距离是0,因为在全局变量区创建，无需专门初始化
|
||
for (int i = 0; i <= n; i++) fa[i] = i;
|
||
char op;
|
||
while (cin >> op) {
|
||
int x, y;
|
||
if (op == 'O') break;
|
||
if (op == 'E') { //查询
|
||
cin >> x;
|
||
find(x); //实现路径压缩，合并了x到根的权值
|
||
printf("%d\n", d[x]); // x到根的权值，记录在d[x]中
|
||
} else {
|
||
//把x的父节点设为y,题目说明了当前的x点是没有父节点的。
|
||
cin >> x >> y;
|
||
//带权并查集中，权是记录在点上的
|
||
//记录自己的点权
|
||
fa[x] = y, d[x] = abs(x - y) % 1000;
|
||
}
|
||
}
|
||
}
|
||
return 0;
|
||
}
|