带权并查集

使用并查集维护序列的追加操作，合并时应该先进行 sz[fy]\(\rightarrow\)dis[fx]，再进行 sz[fy] += sz[fx]。

模板

int find(int x) {
    if(fa[x] == x) return x;
    find(fa[x]);
    dis[x] += dis[fa[x]];
    sz[x] = sz[fa[x]];
    return fa[x] = fa[fa[x]];
}

void merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    fa[fx] = fy;
    dis[fx] = sz[fy];
    sz[fy] += sz[fx];
}