uva 11987 带删除操作的并查集与并查集的可持久化

难点在于操作2，对于叶子结点而言，删除是很简单的，而对于根节点，删除好像是“不可能的”，所以我们可以在初始化的时候动一些脑筋，让每个结点最开始的父亲不是自己而是一个”虚节点（i+n）“，这样所有的结点都变成了叶子结点，然后问题就变得容易解决了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int N = 200001;
 8 int f[N];
 9 ll sum[N];
10 int num[N];
11 int n, m;
12 
13 void init()
14 {
15     for ( int i = 1; i <= n; i++ )
16     {
17         f[i] = i + n;
18     }
19     for ( int i = n + 1; i <= 2 * n; i++ )
20     {
21         f[i] = i;
22         sum[i] = i - n;
23         num[i] = 1;
24     }
25 }
26 
27 int findf( int x )
28 {
29     if ( f[x] != x ) f[x] = findf( f[x] );
30     return f[x];
31 }
32 
33 void union_set( int x, int y )
34 {
35     x = findf(x), y = findf(y);
36     if ( x != y )
37     {
38         f[x] = y;
39         sum[y] += sum[x];
40         num[y] += num[x];
41     }
42 }
43 
44 void move( int x, int y )
45 {
46     int fx = findf(x), fy = findf(y);
47     sum[fx] -= x;
48     num[fx]--;
49     f[x] = fy;
50     sum[fy] += x;
51     num[fy]++;
52 }
53 
54 int main ()
55 {
56     while ( scanf("%d%d", &n, &m) != EOF )
57     {
58         init();
59         while ( m-- )
60         {
61             int op, p, q;
62             scanf("%d", &op);
63             if ( op == 1 )
64             {
65                 scanf("%d%d", &p, &q);
66                 union_set( p, q );
67             }
68             else if ( op == 2 )
69             {
70                 scanf("%d%d", &p, &q);
71                 move( p, q );
72             }
73             else
74             {
75                 scanf("%d", &p);
76                 p = findf(p);
77                 printf("%d %lld
", num[p], sum[p]);
78             }
79         }
80     }
81     return 0;
82 }

还有一种方法叫做”可持久化并查集“，随后补上。