并查集

struct DSU {
    vector<int> f;
    DSU(int N) : f(N) {
        iota(begin(f), end(f), 0);
    }
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        f[y] = x;
    }
    int find(const int x) {
        if (f[x] == x) return x;
        find(f[x]);
        return f[x] = f[f[x]];
    }
    int& operator[](int pos) {
        return f[pos];
    }
}; // DSU

struct Vector {
    int val;
    Vector() = default;
    Vector(int val) : val(val) {}
    Vector operator-() const {
        return Vector(-val);
    }
    friend Vector operator+(const Vector &lhs, const Vector &rhs) {
        int x = lhs.val + rhs.val;
        return Vector(x);
    }
};
struct DSU {
    vector<int> f;
    vector<Vector> val;
    DSU(int N) : f(N), val(N) {
        iota(begin(f), end(f), 0);
    }
    void merge(int x, int y, Vector v) {
        int tx = find(x);
        int ty = find(y);
        if (tx == ty) return;
        val[tx] = val[y] + -val[x] + v;
        f[ty] = ty;
    }
    int find(const int x) {
        if (f[x] == x) return x;
        find(f[x]);
        val[x] = val[x] + val[f[x]];
        return f[x] = f[f[x]];
    }
    Vector query(int x, int y) {
        int tx = find(x);
        int ty = find(y);
        assert(tx == ty);
        return val[x] + -val[y];
    }
    Vector& operator[](int pos) {
        return val[pos];
    }
}; // DSU