#include
using namespace std;
const int maxn = 20000 + 10;
int d[maxn], fa[maxn];
int find(int x)
{
if(x == fa[x]) return x;
else
{
int root = find(fa[x]);
d[x] += d[fa[x]];
return fa[x] = root;
}
}
int main()
{
int T, N, i, I, J;
cin>>T;
while(T--)
{
cin>>N;
for(i = 0; i <= N; i++)
{
fa[i] = i;
d[i] = 0; //自己到自己（根）的距离为0
}
char c;
bool ok = 1;
while(ok && cin>>c)
{
switch(c)
{
case 'O':
{
ok = 0;
break;
}
case 'I':
{
//int x,y;
cin>>I>>J;
/* x=find(I);
y=find(J);
if(x==y) continue;
fa[x]=y;
*/
fa[I] = J;
int ans = I > J (I-J) : (J-I);
d[I] =ans % 1000;
break;
}
case 'E':
{
cin>>I;
find(I);
cout< break;
}
}
}
}
return 0;
}

不能按代码中注释的那样

x=find(I);

y=find(J);

if(x==y) continue;

fa[x]=y;

代替 fa[I] = J;

一换掉就wa

：假设用dis表示点到根的距离

因为为了求dis 所以谁的父亲就是谁的父亲不能压缩，但是上面的find代码是进行压缩的不过它是在递归求dis后才压缩的所以说是可以压缩的

即必须先递归后压缩这样就能保证求出的dis 确实是按照父亲节点算出来的

上面的那个错误是由于先调用find函数压缩，这时候点 I 的 dis还没有算出来，后面再求它的dis的时候其就不再是按照真正的父亲节点找出的而是按照祖先节点算的（因为压缩过了）

对于之后输入E 再次调用fand函数的时候虽然已经压缩过了但是所有点的dis已经求出来了对于再加入的边 I J 我们依旧能够通过接到已经求出的正确dis 求出来I 的dis

注意dis表示点到根的距离

LA 3027 Corporative Network 并查集记录点到根的距离 (二)