POJ 1988 Cube Stacking（带权并查集）

http://poj.org/problem?id=1988

题意：

有n个砖堆，一开始每块砖都位于一个堆，现在有2种操作，操作1是将x所在的砖堆放在y所在砖堆上，操作2是计算x砖下面有多少块砖。

思路：

合并的话容易想到用并查集来维护，由于这里还需要计算每块砖下面的砖数，所以并查集需要带权值。

用ans[x]表示x下面有多少块砖，num[x]表示以x为根的子树有多少个结点。通过路径压缩就可以求出每块砖的答案。

现在看一种情况吧：

用并查集合并只之后就是

将1进行路径压缩时，它首先必须要经过2点，那么2下面的砖块数也是属于1的，所以在路径压缩的时候就可以更新1的答案值，即ans[1]+=ans[2]。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 typedef pair<int,int> pll;
14 const int INF = 0x3f3f3f3f;
15 const int maxn = 30000+5;
16 
17 int n;
18 int p[maxn],num[maxn],ans[maxn];
19 
20 int Find(int x)
21 {
22    if(p[x]==x)  return x;
23    int tmp = p[x];
24    p[x] = Find(p[x]);
25    ans[x] += ans[tmp];
26    return p[x];
27 }
28 
29 int main()
30 {
31    //freopen("in.txt","r",stdin);
32    int n;
33    scanf("%d",&n);
34    for(int i=1;i<maxn;i++)
35    {
36        p[i]=i;
37        num[i]=1;
38        ans[i]=0;
39    }
40    while(n--)
41    {
42        char op[2]; int x, y;
43        scanf("%s",op);
44        if(op[0]=='M')
45        {
46            scanf("%d%d",&x,&y);
47            int xx = Find(x);
48            int yy = Find(y);
49            if(xx!=yy)
50            {
51                p[xx]=yy;
52                ans[xx]+=num[yy];
53                num[yy]+=num[xx];
54            }
55        }
56        else
57        {
58            scanf("%d",&x);
59            Find(x);
60            printf("%d
",ans[x]);
61        }
62    }
63    return 0;
64 }