uvalive 3027 Corporative Network

https://vjudge.net/problem/UVALive-3027

题意：

有n个点，两种操作：

1.E u : 计算u到根节点的距离；

2.I u v : 把v变成u的父亲，并且把它们之间的距离赋值为 |v-u| % 1000。

现在给出若干个这样的操作，对于每个E输出查询结果。

思路：

裸的带权并查集，每次路径压缩都要有d[u] += d[par[u]]；然后每次合并的时候是有方向的，因为指定了父亲和儿子。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int d[20005];
 5 int par[20005];
 6 
 7 int mabs(int x)
 8 {
 9     if (x >= 0) return x;
10     else return -x;
11 }
12 
13 void init(int n)
14 {
15     for (int i = 0;i <= n;i++) par[i] = i;
16 
17     memset(d,0,sizeof(d));
18 }
19 
20 int fin(int x)
21 {
22     if (x == par[x])
23     {
24         return x;
25     }
26     else
27     {
28         int p = par[x];
29 
30         par[x] = fin(p);
31 
32         d[x] += d[p];
33 
34         return par[x];
35     }
36 }
37 
38 int main()
39 {
40     int t;
41 
42     scanf("%d",&t);
43 
44     while (t--)
45     {
46         int n;
47 
48         scanf("%d",&n);
49 
50         init(n);
51 
52         for (;;)
53         {
54             char s[20];
55 
56             scanf("%s",s);
57 
58             if (s[0] == 'O') break;
59 
60             if (s[0] == 'E')
61             {
62                 int x;
63 
64                 scanf("%d",&x);
65 
66                 fin(x);
67 
68                 printf("%d
",d[x]);
69             }
70             else
71             {
72                 int x,y;
73 
74                 scanf("%d%d",&x,&y);
75 
76                 d[x] = mabs(x - y)  % 1000;
77 
78                 par[x] = y;
79             }
80         }
81     }
82 
83     return 0;
84 }