UVA1329 Corporative Network（并查集）

题意：有N个结点，初始时每个结点的父节点都不存在。你的任务是执行一次I操作和E操作，格式如下。

I u v:把结点u的父节点设为v，距离为|u-v|除以1000的余数。输入保证执行指令前u没有父节点。

E u:询问u到根节点的距离

分析：因为题目只查询结点到根节点的距离，所以每棵树除了根节点不能换之外，其他结点的位置可以任意改变，这恰好符合并查集的特点，但是需要记录附加信息。

// File Name: 1329.cpp
// Author: zlbing
// Created Time: 2013/3/8 22:06:16

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<n+1;i++)
#define MAXN 20050
int f[MAXN];
int d[MAXN];
int find(int x){
    if(x==f[x])return x;
    int a=find(f[x]);
    d[x]=d[f[x]]+d[x];
    f[x]=a;
    return f[x];
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        char ch[3];
        scanf("%d",&n);
        REP1(i,n)f[i]=i;
        REP1(i,n)d[i]=0;
        while(scanf("%s",ch)){
            if(ch[0]=='O')break;
            if(ch[0]=='I'){
                int a,b;
                scanf("%d%d",&a,&b);
                f[a]=b;
                d[a]=abs(a-b)%1000;
            }
            else{
                int a;
                scanf("%d",&a);
                find(a);
                printf("%d\n",d[a]);
            }
        }
    }
    return 0;
}