2种操作 I u v 把u的父节点设为v 距离为fabs(u-v)%1000 E u求u到根节点的距离
设dis[i] 为i节点到父节点的距离
在并查集压缩路径时更新dis数组
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 20010;
int dis[maxn], pa[maxn];
int find(int x)
{
if(x != pa[x])
{
int root = find(pa[x]);
dis[x] += dis[pa[x]];
pa[x] = root;
return pa[x];
}
else
return x;
}
int main()
{
int T, n;
int u, v;
scanf("%d", &T);
while(T--)
{
char s[10];
scanf("%d", &n);
for(int i = 0; i <= n; i++)
{
pa[i] = i;
dis[i] = 0;
}
while(scanf("%s", s) && s[0] != ‘O‘)
{
if(s[0] == ‘E‘)
{
scanf("%d", &u);
find(u);
printf("%d\n", dis[u]);
}
else
{
scanf("%d %d", &u, &v);
dis[u] = abs(u-v) % 1000;
pa[u] = v;
}
}
}
return 0;
}