本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1196
又是一道带权并查集的题，没太多难度，就是吧。。。
为了提高代码能力，换了一种更松散的代码风格，导致之前的读入优化有一行很长，所以就去抄了某位大佬的模板，结果被带跑了。。。
读入字符时傻了一样“跳”着读，结果全TLE了。。。
说正事，显然我们需要维护每个结点到其祖先的距离，而这个距离恰好是该结点之前的结点个数，因此我们还需要维护每个并查集的结点个数，注意，只需要维护祖先的就可以，其他结点可以找到祖先，然后查询祖先的即可。
然后就是查询时要加绝对值，然后还要减1，这题坑基本没有，还算友好。
1 #include <cstdio> 2 #include <cmath> 3 4 inline int get_num() { 5 int num = 0; 6 char c = getchar(); 7 while (c < '0' || c > '9') c = getchar(); 8 while (c >= '0' && c <= '9') 9 num = num * 10 + c - '0', c = getchar(); 10 return num; 11 } 12 13 const int maxn = 3e4 + 5; 14 15 int fa[maxn], dist[maxn], size[maxn]; 16 17 int dj_find(int i) { 18 if (i == fa[i]) return i; 19 int old = fa[i]; 20 fa[i] = dj_find(old); 21 dist[i] += dist[old]; 22 return fa[i]; 23 } 24 25 inline void dj_merge(int a, int b) { 26 a = dj_find(a), b = dj_find(b); 27 if (a != b) { 28 fa[a] = b; 29 dist[a] += size[b]; 30 size[b] += size[a]; 31 } 32 } 33 34 int main() { 35 for (int i = 1; i <= 30000; ++i) 36 fa[i] = i, dist[i] = 0, size[i] = 1; 37 int t, a, b; 38 char c; 39 t = get_num(); 40 for (int i = 1; i <= t; ++i) { 41 c = 0; //此处史无前例的坑！ 42 while (c != 'M' && c != 'C') 43 c = getchar(); 44 a = get_num(), b = get_num(); 45 if (c == 'M') dj_merge(a, b); 46 else { 47 if (dj_find(a) != dj_find(b)) printf("-1 "); 48 else printf("%d ", abs(dist[a] - dist[b]) - 1); 49 } 50 } 51 return 0; 52 }