あ、値集約付きpotentialdsu（ネイティブ発音）...

template <class S, S (*op)(S, S), typename T> struct potential_dsu {
    using vi = vec<int>;
    using vvi = vec<vi>;
    vi par, sz, es;
    vec<T> h;
    int cc;
    vector<S> dat;
    vvec<int> ms;

    potential_dsu(const vector<S> d) : dat(d) {
        int n = d.size();
        par = vi(n);
        sz = vi(n, 1);
        es = vi(n, 0);
        cc = n;
        iota(all(par), 0);
        ms.resize(n);
        rep(i, 0, n) ms[i].pb(i);
        h = vec<T>(n, 0);
    }

    int leader(int u) {
        if (par[u] != u) {
            int r = leader(par[u]);
            h[u] += h[par[u]];
            return par[u] = r;
        }
        return u;
    }

    bool same(int a, int b) { return leader(a) == leader(b); }

    vec<int> merge(int s, int t, T w) {
        // h[t] = h[s] + w 或いは s -> tに重みwの辺　
        vec<int> R;

        w += weight(s), w -= weight(t);
        s = leader(s), t = leader(t);
        if (s == t) {
            es[s]++;
            return R;
        }

        if (sz[s] < sz[t]) {
            swap(s, t);
            w *= -1;
        }

        cc--;
        par[t] = s;
        sz[s] += sz[t];
        es[s] += es[t] + 1;
        bool f = false;
        if (dat[s] == -1) swap(s, t), f = true;

        ll ret = dat[s];
        for (auto v : ms[t]) {
            to[v] = ret;
            if (ret != -1) R.pb(v);
        }
        if (f) swap(s, t);

        for (auto v : ms[t]) ms[s].pb(v);

        dat[s] = op(dat[s], dat[t]);
        h[t] = w;
        return R;
    }

    T weight(int v) {
        //根から見たvの値
        leader(v);
        return h[v];
    }

    T diff(int s, int t) {  // sから見た tの値
        return weight(t) - weight(s);
    }
    S value(int u) { return dat[leader(u)]; }
};

Tがpotentialの方こういう時potential_typeとか書いてあると嬉しいね書かないが

Astral-23 / competitive-programing

あ、値集約付きpotentialdsu（ネイティブ発音）... #63