? 第一种是移动操作，格式为“移动X到Y的上面”。X和Y代表两块积木的编号，意思是将X所的那堆积木，整体叠放到Y所在的那堆积木之上；“M”
? 第二种是统计操作，格式为“统计Z下方的积木数量”。Z代表一块积木的编号，意思是贝西需要报告在编号为Z的积木之下还有多少块积木；“C”
显然的带权并查集，其实是多维护了两个变量，注意查询时一定要先更新，防止查询时未被更新而出错
#include<bits/stdc++.h> #define N 300000 using namespace std; int n,fa[N],front[N],num[N];
//num表示以x为底的上面的集合中元素数量
//front就是x距低端的元素数量 int find(int x){ if(x==fa[x]) return x; int f=find(fa[x]); front[x]+=front[fa[x]]; return fa[x]=f; } int main() { scanf("%d",&n); for(int i=1;i<N;i++) fa[i]=i,num[i]=1; for(int x,y,z,i=1;i<=n;i++){ char a; cin>>a; if(a==‘M‘){ scanf("%d%d",&x,&y); int fx=find(x),fy=find(y); fa[fx]=fy;//更新父节点 front[fx]+=num[fy];//更新儿子的front num[fy]+=num[fx];//更新父亲的num num[fx]=0;//将儿子的num归0 } else { scanf("%d",&z); x=find(z);//一定要先查询在输出 printf("%d\n",front[z]); } } return 0; }
相同题目见：https://www.cnblogs.com/song-/p/9620959.html
原文：https://www.cnblogs.com/song-/p/9625401.html