Luogu P1196 [NOI2002]银河英雄传说 带权并查集
对于每一列记录id[i]表示第i号战舰的序号，sum[i]表示第i号战舰所在列的战舰个数
对于每一个合并操作，无法对每一个所在当前列的战舰信息进行更新
所以只对队头战舰的信息进行修改，用类似线段树中懒标记的方法
当要对这一艘战舰进行访问时，对其信息进行修改
注意，在并查集中先要对其列首战舰进行更新，在对当前战舰更新
#include <bits/stdc++.h> using namespace std; const int MAXN=31000; int t,fa[MAXN],id[MAXN],sum[MAXN]; inline int find(int x) { if (fa[x]==x) return fa[x]; int f; f=fa[x]; fa[x]=find(fa[x]);//注意 id[x]+=id[f];//在父亲更新后更新当前 return fa[x]; } int main() { scanf("%d",&t); for (int i=1;i<=30010;i++)//初始化 { sum[i]=1; fa[i]=i; id[i]=0; } for (int i=1;i<=t;i++) { char ch[10]; int a,b; scanf("%s%d%d",ch,&a,&b); if (ch[0]=='M') { if (find(a)!=find(b)) { int ga,gb; ga=find(a); gb=find(b); id[ga]+=sum[gb]; sum[gb]+=sum[ga]; sum[ga]=0; fa[ga]=gb; } } else { if (find(a)!=find(b)) printf("-1 "); else printf("%d ",abs(id[b]-id[a])-1); } } }