View Code of Problem 1047

#include <iostream>

using namespace std;

const int maxn = 20000 + 10;        //企业数5 <= N <= 20000

int d[maxn], fa[maxn];      //d[i]点i到根结点的距离（但初始化后第一次给的值是i到其父结点的距离），fa[i]为结点i的父结点

int find(int x)     //带路径压缩的查找函数
{
    if(x == fa[x]) return x;
    else
    {
        int root = find(fa[x]);
        d[x] += d[fa[x]];       //改为到根的距离，这里不需考虑是否要对1000取模
        return fa[x] = root;        //路径压缩
    }
}

int main()
{
    int T, N, i, I, J;
    cin>>T;
    while(T--)
    {
        cin>>N;
        for(i = 0; i <= N; i++)     //初始化
        {
            fa[i] = i;      //根树
            d[i] = 0;       //自己到自己（根）的距离为0
        }
        char c;
        bool ok = 1;        //是否退出的标记
        while(ok && cin>>c)
        {
            switch(c)
            {
                case 'O':
                    {
                        ok = 0;
                        break;
                    }
                case 'I':
                    {
                        cin>>I>>J;
                        fa[I] = J;
                        int ans = I > J ? (I-J) : (J-I);
                        d[I] = ans % 1000;      //赋该点到其父结点的距离值
                        break;
                    }
                case 'E':
                    {
                        cin>>I;
                        find(I);        //find会维护（将d[I]改为该点到根的距离）该点到根的距离
                        cout<<d[I]<<endl;
                        break;
                    }
            }
        }
    }
    return 0;
}