一、题目回顾
题目链接：Cube Stacking
题意：有n个箱子，初始时每个箱子单独为一列；接下来有p行输入，M, x, y 或者 C, x；
- 对于M,x,y：表示将x箱子所在的一列箱子搬到y所在的一列箱子上；
- 对于C,x：表示求箱子x下面有多少个箱子；
输出：在箱子x所在的那列中，求出在x之下的cube的个数。
二、解题分析
知识点：带权并查集
解题思路
- 初级：M x y是将x所在列的所有箱子叠到y所在列的上面，如果直接模拟的话就是将x最末端的叶子节点当做y的根节点的父亲节点合并，不过那样的话不好压缩路径，不压缩路径的话会超时.......
- 高级：用数组s存储当前节点x的子结点数量，用数组d存储当前节点到根节点的距离，所求值即s[find(x)]-d[x]，（也许你会说要求的不就是s[x]吗，道理是这样，但我们并没有求出每个节点的子结点数量）
- 续上高级：按照一般并查集的合并方法，令pre[find(y)]=find(x)；那合并后会有: d[find(y)]=s[find(x)]+1，s[find(x)]+=s[find(y)]+1 。（不清楚可以自己在草稿纸上画图确定）
重要之处
- 多了两个结点之间的关系
- d[x]表示结点x到根的距离
- s[x]表示在结点x下cube的数量
- 然后在find函数、unite函数内维持这两个数组即可
代码：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int p; int pre[30005]; int d[30005]; //d[x]表示结点x到根的距离 int s[30005]; //s[x]表示在结点x下cube的数量 void init() { for(int i=1;i<=30005;i++){ pre[i] = i; // d[i] = 0; 加上这个就 WA s[i] = 0; } } int find(int x) { if(x==pre[x]) return x; int t = pre[x]; //***递归思想，t为存储x改变根节点后的根节点的临时变量 pre[x] = find(pre[x]); d[x] = d[x] + d[t]; //***x到改变前根节点的距离即x到t的距离加上t到根节点的距离 return pre[x]; } void unite(int x,int y) { int fx = find(x); int fy = find(y); if(fx != fy){ pre[fy] = fx; //***将x所在列放到y所在列上面后，find(y)到新合并后的根节点的距离即为合并前find(x)的子树的大小 d[fy] = s[fx]+1; s[fx] = s[fx]+(s[fy]+1); //***合并后find(x)的子树大小即为合并前find(x)与find(y)的子树大小的和 } } int main() { cin>>p; init(); char ch; int x,y; getchar(); while(p--){ scanf("%c",&ch); if(ch=='M'){ scanf("%d%d",&x,&y); unite(x,y); } if(ch=='C'){ scanf("%d",&x); //***注意这里并不是输出son(x)，因为我们并没有求出每个节点的子树的大小 printf("%d ",s[find(x)]-d[x]); } getchar(); } return 0; }