src/dsu_weighted.hpp

View this file on GitHub
Last update: 2025-10-07 04:08:36+09:00
Include: #include "src/dsu_weighted.hpp"

Depends on

src/template.hpp

Code

#include "template.hpp"

template<typename T> struct dsu_weighted {
    vector<int> p;
    vector<T> w;
    dsu_weighted(int n): p(n, -1), w(n, 0) {}
    bool same(int a, int b) { return leader(a) == leader(b); }
    int leader(int a) {
        return p[a] < 0 ? a : (leader(p[a]), w[a] += w[p[a]], p[a] = leader(p[a]));
    }
    int size(int a) { return -p[leader(a)]; }
    int merge(int a, int b, long c) {
        c += weight(a), c -= weight(b);
        a = leader(a), b = leader(b);
        if(a == b) return a;
        if(p[a] > p[b]) swap(a, b), c *= -1;
        p[a] += p[b];
        p[b] = a;
        w[b] = c;
        return a;
    }
    T weight(int a) {
        leader(a);
        return w[a];
    }
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 2 "src/dsu_weighted.hpp"

template<typename T> struct dsu_weighted {
    vector<int> p;
    vector<T> w;
    dsu_weighted(int n): p(n, -1), w(n, 0) {}
    bool same(int a, int b) { return leader(a) == leader(b); }
    int leader(int a) {
        return p[a] < 0 ? a : (leader(p[a]), w[a] += w[p[a]], p[a] = leader(p[a]));
    }
    int size(int a) { return -p[leader(a)]; }
    int merge(int a, int b, long c) {
        c += weight(a), c -= weight(b);
        a = leader(a), b = leader(b);
        if(a == b) return a;
        if(p[a] > p[b]) swap(a, b), c *= -1;
        p[a] += p[b];
        p[b] = a;
        w[b] = c;
        return a;
    }
    T weight(int a) {
        leader(a);
        return w[a];
    }
};