1.题目描述：点击打开链接
2.解题思路：本题利用并查集解决。因为从题目的要求可知，只涉及距离查询到根结点的距离，因此除了根结点外，其他结点的位置可以任意改变，，只是要维护到父结点的距离。当进行路径压缩时，更新这个距离值即可。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 20000+10int pa[N], d[N];int findset(int x){if (pa[x] != x){int root = findset(pa[x]);//找到根结点d[x] += d[pa[x]];//更新d[x]return pa[x] = root;//路径压缩，将x的父结点直接修改为根结点}else return x;}int main(){//freopen("t.txt", "r", stdin);int T;scanf("%d", &T);while (T–){int n, u, v;char cmd[9];scanf("%d", &n);for (int i = 1; i <= n; i++){pa[i] = i;d[i] = 0;}while (scanf("%s", cmd) && cmd[0] != 'O'){if (cmd[0] == 'E'){scanf("%d", &u);findset(u);//查询距离时才进行路径压缩printf("%d\n", d[u]);}if (cmd[0] == 'I'){scanf("%d%d", &u, &v);pa[u] = v;d[u] = abs(u – v) % 1000;}}}return 0;}
仿佛松树就是一位威风的将军，守护着国家的国民。
