题目：https://www.luogu.org/problemnew/show/P1196
关键点在于存下每个点的位置。
自己糊涂的地方：位置是相对于谁的位置？
因为每次给一个原来是fa的点赋位置时，赋的位置与此点的新fa有关，故很容易想到在 find() fa 时顺便更新 位置 们。
所以每次存的位置应该是新fa的集的大小——不能加上新fa自己的位置，那样就混乱了。
要点在于若想在 find() 更新 fa 时同步更新 pos，则存的位置必须是 相对于自己当前 fa 的位置！
自己的难点：怎样做到递归同步更新pos？
递归的要点是先运行一遍更深层的，则更深层的地方就被赋好了值，就可以更新当前层了。
所以不能按平常写法：return fa[a]=find(fa[a])；而要在 find() 和 return 中间插一个更新pos的语句！
#include<iostream> #include<cstdio> using namespace std; int t,a,b,fa[30005],pos[30005],siz[30005];//pos是相对自己的fa的位置(无自己，有fa)， char c; //只有这样才能更新fa时同步更新pos int find(int a) { if(fa[a]==a)return a; int k=find(fa[a]); pos[a]+=pos[fa[a]]; return fa[a]=k; } int main() { for(int i=1;i<=30000;i++)fa[i]=i,siz[i]=1; scanf("%d",&t); while(t--) { scanf(" %c%d%d",&c,&a,&b); if(c=='M') { int u=find(a); int v=find(b); fa[u]=v; pos[u]=siz[v]; siz[v]+=siz[u]; } if(c=='C') { int u=find(a); int v=find(b); if(u!=v)printf("-1 "); else { int k=pos[a]-pos[b]; if(k<0)k=-k; printf("%d ",k-1); } } } return 0; }