@[灰狼与蔷薇](/space/show?uid=28910)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=30005;
int fa[MAX_N];
int dis[MAX_N];
int siz[MAX_N];
int find(int x)
{
// cout<<x<<endl;
if(fa[x]==x)return x;
else
{
int to=find(fa[x]);
dis[x]+=dis[fa[x]];
fa[x]=to;
return to;
}
}
void unite(int u,int v)
{
int fu=find(u);
int fv=find(v);
if(fu==fv)return;
fa[fu]=fv;
dis[fu]=siz[fv];
siz[fv]+=siz[fu];
}
int query(int u,int v)
{
if(find(u)!=find(v))return -1;
return abs(dis[u]-dis[v])-1;
}
int main()
{
for(int i=0;i<MAX_N;i++)
{
fa[i]=i;
dis[i]=0;
siz[i]=1;
}
int T;
cin>>T;
while(T--)
{
string op;
int u,v;
cin>>op>>u>>v;
if(op=="M")unite(u,v);
else cout<<query(u,v)<<endl;
// for(int i=1;i<=4;i++)cout<<fa[i]<<" \n"[i==4];
// for(int i=1;i<=4;i++)cout<<dis[i]<<" \n"[i==4];
// for(int i=1;i<=4;i++)cout<<siz[i]<<" \n"[i==4];
}
return 0;
}
```
by Smile_Cindy @ 2019-05-01 19:09:32
@[灰狼与蔷薇](/space/show?uid=28910)
改过了,已AC
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define Ship 30001
int f[Ship],val[Ship],size[Ship];
int T,x,y;
char cz;
void read(int &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') {
fh=-1;ch=getchar();
}
else fh=1;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
}x*=fh;
}
void read(char &x){
x=getchar();
while(x!='M'&&x!='C') x=getchar();
}
void clear(){
int i=Ship;
while(--i){
f[i]=i,val[i]=0,size[i]=1;
}
}
int find(int x)
{
// cout<<x<<endl;
if(f[x]==x)return x;
else
{
int to=find(f[x]);
val[x]+=val[f[x]];
f[x]=to;
return to;
}
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
f[fx]=fy;
val[fx]+=size[fy];
size[fy]+=size[fx];
}
}
void query(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) puts("-1");
else printf("%d\n",abs(val[x]-val[y])-1);
}
int main(){
clear();
read(T);
while(T--){
read(cz);read(x);read(y);
if(cz=='M') merge(x,y);
else query(x,y);
}
return 0;
}
```
by Smile_Cindy @ 2019-05-01 19:10:53
这题不是splay吗?(
by NaCly_Fish @ 2019-05-01 19:15:57
~~为什么不fhq treap~~
by cosmicAC @ 2019-05-01 19:17:13
@[灰狼与蔷薇](/space/show?uid=28910) %lbn
by ZigZagKmp @ 2019-05-01 19:55:50
@[Alpha](/space/show?uid=87058) 非常感谢,能请您告诉我是哪里写错了吗
by 览遍千秋 @ 2019-05-01 21:36:07
@[Alpha](/space/show?uid=87058) 是不是因为在find函数中,更新val[x]之前,要对val[f[x]]进行一次路径压缩,即更新?
by 览遍千秋 @ 2019-05-01 21:47:15
@[灰狼与蔷薇](/space/show?uid=28910)
Yes
by Smile_Cindy @ 2019-05-01 22:06:58
初三AFO。。。。
高中的表示不服
by Andrew82 @ 2019-07-25 08:08:09