图论

struct Dsu {
    vector<int> p, sz;

    Dsu() {}
    Dsu(int n) : p(n + 1) ,{
        p.resize(n + 1);
        sz.resize(n + 1);
        init(n);
    }

    void init(int n) {
        for (int i = 0; i <= n; i++) {
            p[i] = i;
            sz[i] = 1;
        }
    }

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
		return p[x];
    }

    bool merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return false;
        p[fy] = fx;
        sz[fx] += sz[fy];
        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return sz[find(x)];
    }
};

struct DIJ {
    int n;
    vector<int> dist;
    vector<vector<pii>> adj;

    DIJ() {}
    DIJ(int n) {
        this->n = n;
        adj.resize(n + 1);
    }

    void add(int u, int v, int w) {
        adj[u].push_back({v, w});
    }

    void dijkstra(int s) {
        dist.assign(n + 1, 1e18);
        dist[s] = 0;

        priority_queue<pii, vector<pii>, greater<pii>> pq;
        vector<bool> vis(n + 1, false);
        pq.push({0, s});

        while (pq.size()) {
            auto [d, cur] = pq.top();
            pq.pop();

            if (vis[cur]) continue;
            vis[cur] = true;

            for (auto [nxt, w] : adj[cur]) {
                if (dist[nxt] > dist[cur] + w) {
                    dist[nxt] = dist[cur] + w;
                    pq.push({dist[nxt], nxt});
                }
            }
        }
    }
};

struct LCA {
    int root;
    vector<vector<int>> adj;
    vector<int> dep, father, sz, heavy, top;

    LcA () {}
    LCA (int root, vector<vector<int>> adj) {
        init(root, adj);
    }

    void init(int root, vector<vector<int>> adj) {
        this->root = root;
        this->adj = adj;
        int n = adj.size();
        dep.resize(n), father.resize(n), sz.resize(n), heavy.resize(n), top.resize(n);
        dfs1(root, root), dfs2(root, root);
    }

    void dfs1(int cur, int fa) {
        father[cur] = fa;
        sz[cur] = 1;
        dep[cur] = dep[fa] + 1;
        for (auto son : adj[cur]) {
            if (son == fa) continue;
            dfs1(son, cur);
            sz[cur] += sz[son];
            if (sz[heavy[cur]] < sz[son]) heavy[cur] = son;
        }
    }

    void dfs2(int cur, int head) {
        top[cur] = head;
        if (!heavy[cur]) return;
        dfs2(heavy[cur], head);
        for (auto son : adj[cur]) {
            if (son == father[cur] || son == heavy[cur]) continue;
            dfs2(son, son);
        }
    }

    int query(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) swap(x, y);
            x = father[top[x]];
        }
        return dep[x] < dep[y] ? x : y;
    }
};