切切水题，并查集。
记录当前根树的结点个数，记录每个结点相对根结点的转移次数。1y~
代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring> using namespace std;
const int N = ;
struct MFS {
int fa[N], tm[N], cnt[N];
void init() { for (int i = ; i < N; i++) fa[i] = i, tm[i] = , cnt[i] = ;}
int find(int x, int &t) {
if (fa[x] == x) {
t = ;
} else {
fa[x] = find(fa[x], t);
tm[x] += t;
t = tm[x];
}
return fa[x];
}
void merge(int x, int y) {
int tmp;
int fx = find(x, tmp);
int fy = find(y, tmp);
tm[fy] -= tm[fx] - ;
cnt[fx] += cnt[fy];
fa[fy] = fa[fx];
// for (int i = 0; i < 5; i++) cout << fa[i] << ' '; cout << endl;
}
void query(int x) {
int tmp;
int fx = find(x, tmp);
printf("%d %d %d\n", fx, cnt[fx], tm[x] + tm[fx]);
}
} mfs; int main() {
int T, n, m;
scanf("%d", &T);
for (int cas = ; cas <= T; cas++) {
scanf("%d%d", &n, &m);
mfs.init();
char op[];
int x, y;
printf("Case %d:\n", cas);
for (int i = ; i < m; i++) {
scanf("%s", op);
if (op[] == 'T') {
scanf("%d%d", &x, &y);
mfs.merge(y, x);
} else {
scanf("%d", &x);
mfs.query(x);
}
}
}
return ;
}
——written by Lyon