POJ 1988 Cube Stacking

题意：有编号为1~N的N个小木块，有两种操作

1. M x y 将木块x所在的堆放到木块y所在的堆的上面
2. C x 询问木块x下面有多少块木块

代码巧妙就巧妙在GetParent函数中在进行路径压缩的同时，也计算好了该木块对应的under值

这个需要好好体会

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 int parent[maxn], under[maxn], sum[maxn];

 int GetParent(int a)

 {

     if(parent[a] == a)

         return a;

     int t = GetParent(parent[a]);

     under[a] += under[parent[a]];

     parent[a] = t;

     return t;

 }

 void Merge(int a, int b)

 {

     int pa = GetParent(a);

     int pb = GetParent(b);

     if(pa == pb)    return;

     parent[pb] = pa;

     under[pb] = sum[pa];

     sum[pa] += sum[pb];

 }

 int main(void)

 {

     #ifdef LOCAL

         freopen("1988in.txt", "r", stdin);

     #endif

     for(int i = ; i < maxn; ++i)

     {

         parent[i] = i;

         under[i] = ;

         sum[i] = ;

     }

     int n;

     scanf("%d", &n);

     getchar();

     for(int i = ; i < n; ++i)

     {

         char p;

         scanf("%c", &p);

         if(p == 'M')

         {

             int a, b;

             scanf("%d%d", &a, &b);

             getchar();

             Merge(b, a);

         }

         else

         {

             int a;

             scanf("%d", &a);

             getchar();

             GetParent(a);

             printf("%d\n", under[a]);

         }

     }

     return ;

 }

代码君