大意：你有30000个队列，第i个队列中只有i

有T个操作，1，把某个队列头接到另一个队列尾。

2，问两个元素之间的距离。

本题主要有三种解法。

①带权并查集。

具体来说就是，并查集维护当前集合的大小，这个点距离代表元(队首)的边数。

然后把合并和路径压缩魔改一下。询问的时候就直接取距离之差。

1 #include 
      
        2  3 const int N = 30010; 4  5 int fa[N], sum[N], siz[N]; 6 char str[5]; 7  8 inline int find(int x, int &s) { 9     if(fa[x] == x) {10         s = 0;11         return x;12     }13     int t = find(fa[x], s);14     s += sum[x];15     sum[x] = s;16     return fa[x] = t;17 }18 19 inline void merge(int x, int y) {20     int a, b;21     x = find(x, a);22     y = find(y, b);23     fa[x] = y;24     sum[x] = siz[y];25     siz[y] += siz[x];26     return;27 }28 29 inline int ask(int x, int y) {30     int a, b;31     x = find(x, a);32     y = find(y, b);33     if(x != y) {34         return -1;35     }36     return (a > b ? a - b : b - a) - 1;37 }38 39 int main() {40     int n;41     scanf("%d", &n);42     for(int i = 1; i <= 30000; i++) {43         fa[i] = i;44         siz[i] = 1;45     }46     for(int i = 1, x, y; i <= n; i++) {47         scanf("%s%d%d", str, &x, &y);48         if(str[0] == 'M') {49             merge(x, y);50         }51         else {52             printf("%d\n", ask(x, y));53         }54     }55 56     return 0;57 }
      

②平衡树

这个太暴力了......开30000颗平衡树即可。

③离线(kruskal重构树)

重构的时候把顺序搞一下，然后提出来DFS序，直接回答询问。