哈哈，一次AC。
题意：给你 1-n 编号的立方体，然后移动包含指定编号的立方体的堆移到另一个堆上边，
询问指定的编号立方体下面有多少个立方体。
思路：由于并查集是存储的是它的父亲，那么只能从父亲那里更新数据，即只能往上推，不能往下推。
所以我干脆倒过来思考，它让我求编号为i的立方体下面有多少立方体，
那么我只要求在它上方的立方体个数，假设为m。以及整个堆中立方体的个数tot，则答案为tot-m-1,1为它自己。
开一个数组upnum，存储编号为i的立方体上方的立方体个数。
每次再查找父节点路径压缩之前先更新，从最顶层即根节点往底层更新
#include#include #include #include #include #include using namespace std;const int maxn=30010;int father[maxn];int ranks[maxn]; //表示以i为根节点的集合中所含有的个数int upnum[maxn]; //upnum[i]表示在i顶上的骰子个数int p,q;void init(){ for(int i=0;i<=maxn;i++){ father[i]=i; ranks[i]=1; }}//x的父节点更新完相应的upnum后，才能更新x的upnumint update(int x){ if(father[x]==x) return upnum[x]; else{ upnum[x]+=update(father[x]); return upnum[x]; }}int find_root(int x){ if(father[x]!=x){ father[x]=find_root(father[x]); } return father[x];}void Union(int a,int b){ upnum[a]+=update(father[a]); upnum[b]+=update(father[b]); int x=find_root(a); int y=find_root(b); if(x==y) return; father[y]=x; upnum[y]+=ranks[x]; ranks[x]+=ranks[y];}int main(){ int a,b; char ch[4]; scanf("%d",&p); memset(upnum,0,sizeof(upnum)); init(); for(int i=1;i<=p;i++){ scanf("%s",ch); if(ch[0]=='M'){ scanf("%d%d",&a,&b); Union(a,b); } else{ scanf("%d",&a); upnum[a]+=update(father[a]); int root=find_root(a); //求在a下方的立方体个数 int downnum=ranks[root]-upnum[a]-1; printf("%d\n",downnum); } } return 0;}