带权并查集

带权并查集维护任意两点之间具有可加、可差分性质的路径信息。

TODO

封装模板。

操作

路径压缩

int query(int x) {
    if (x == c[x]) return x;
    int old_fa = c[x];
    c[x] = query(c[x]);
    val[x] += val[old_fa];
    return c[x];
}

合并

由于任意两点之间路径权值应该相同，所以可以得到

void merge(int u, int v, int w) {
    if (connected(u, v)) return;
    int u_root = query(u), v_root = query(v);
    c[u_root] = v_root;
    val[u_root] = - val[u] + val[v] + w;
}