题目大意
不说了。到处都有题面
并查集
傻了傻了！！！
前两天做了两道并查集按秩合并，然后看到这题，就很愉快地打了并查集按秩合并加个懒标记，对了之后看别人的AC程序，怎么，这么暴力啊啊啊啊啊啊
由于并查集按秩合并的树高是log的，所以我们维护每个点在其舰队中的位置编号，然后对于合并，很明显的是有一棵树的编号都加上一个同样的值，于是就可以打标记，查询时再像splay的clear一样将到根路径上的标记下传
贴个无脑代码。。。。。
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;typedef long long LL;
typedef double db;int get(){char ch;int s=0;bool pd=0;while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');if (ch=='-')pd=1;else s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';if (pd)return -s;return s;
}const int N = 30010;struct point{int add,dep,fa,v,size;
}a[N];
int t,n;
struct edge{int x,next;
}e[N];
int h[N],tot;
int q[N],k;void inse(int x,int y){e[++tot].x=y;e[tot].next=h[x];h[x]=tot;
}int getfather(int x){if (!a[x].fa)return x;return getfather(a[x].fa);
}void down(int x){if (a[x].add){for(int p=h[x];p;p=e[p].next){a[e[p].x].add+=a[x].add;a[e[p].x].v+=a[x].add;}a[x].add=0;}
}void clear(int x){k=0;while(x){q[++k]=x;x=a[x].fa;}fd(i,k,1)down(q[i]);
}int main(){freopen("galaxy.in","r",stdin);freopen("galaxy.out","w",stdout);n=30000;fo(i,1,n){a[i].add=a[i].fa=0;a[i].dep=a[i].v=a[i].size=1;}t=get();fo(i,1,t){char ch;while(ch=getchar(),ch!='M'&&ch!='C');int x=get(),y=get(),tx=getfather(x),ty=getfather(y);switch(ch){case 'M':x=tx,y=ty;if (x!=y){if (a[x].dep<=a[y].dep){down(y);a[x].add+=a[y].size;a[x].v+=a[y].size;a[y].size+=a[x].size;a[x].fa=y;inse(y,x);a[y].dep=max(a[y].dep,a[x].dep+1);}else{a[x].add+=a[y].size;a[x].v+=a[y].size;down(x);a[x].size+=a[y].size;a[y].fa=x;inse(x,y);a[x].dep=max(a[x].dep,a[y].dep+1);}}break;case 'C':if (tx!=ty)printf("-1\n");else{clear(x);clear(y);printf("%d\n",abs(a[x].v-a[y].v)-1);}break;}}fclose(stdin);fclose(stdout);return 0;
}