#include <bits/stdc++.h>
using namespace std;

// ── 并查集（DSU）──────────────────────────────────
struct DSU {
    vector<int> parent, rank_;
    int components;

    DSU(int n) : parent(n), rank_(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // 路径压缩
        return parent[x];
    }

    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;           // 已在同一分量中
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;                      // 将秩小的挂到秩大的下面
        if (rank_[x] == rank_[y]) rank_[x]++;
        components--;
        return true;
    }

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

// ── Kruskal MST ────────────────────────────────────
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;  // n 个顶点，m 条边

    // edges[i] = {权重, u, v}
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w, u, v] : edges) {
        cin >> u >> v >> w;
        u--; v--;  // 0-indexed
    }

    sort(edges.begin(), edges.end());  // 按权重排序（第一个元素）

    DSU dsu(n);
    long long mst_weight = 0;
    int edges_added = 0;
    vector<pair<int,int>> mst_edges;

    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) {      // 仅在不构成环时加边
            mst_weight += w;
            mst_edges.push_back({u, v});
            edges_added++;
            if (edges_added == n - 1) break;  // MST 构建完成
        }
    }

    if (edges_added < n - 1) {
        cout << "图不连通——MST 不存在\n";
    } else {
        cout << "MST 权重：" << mst_weight << "\n";
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // 邻接表：adj[u] = {边权, 邻居} 的列表
    vector<vector<pair<int,int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});  // 无向图
    }

    // 用小根堆实现 Prim
    vector<bool> in_mst(n, false);
    long long mst_weight = 0;
    int edges_added = 0;

    // 小根堆：{边权, 顶点}
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});  // 从顶点 0 出发，代价 0

    while (!pq.empty() && edges_added < n) {
        auto [w, u] = pq.top(); pq.pop();

        if (in_mst[u]) continue;  // 已加入 MST，跳过（懒惰删除）
        in_mst[u] = true;
        mst_weight += w;
        edges_added++;

        for (auto [edge_w, v] : adj[u]) {
            if (!in_mst[v]) {
                pq.push({edge_w, v});  // 候选扩展边
            }
        }
    }

    if (edges_added < n) {
        cout << "图不连通\n";
    } else {
        cout << "MST 权重：" << mst_weight << "\n";
    }

    return 0;
}

示例 MST 边（已排序）：(0,1,w=1)、(1,2,w=2)、(2,3,w=3)

合并 (0,1,w=1) 后：  节点 4（w=1）
                      / \
                     0   1

合并 (1,2,w=2) 后：  节点 5（w=2）
                      / \
                节点4    2
                (w=1)
                 / \
                0   1

合并 (2,3,w=3) 后：  节点 6（w=3）
                      / \
                  节点5   3
                  (w=2)
                   / \
                节点4  2
                (w=1)
                 / \
                0   1

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, rank_, root;  // root[i] = 以 i 为根的分量在 Kruskal 树中的根节点
    DSU(int n) : parent(n), rank_(n, 0), root(n) {
        iota(parent.begin(), parent.end(), 0);
        iota(root.begin(), root.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    // 返回此次合并创建的新 Kruskal 树节点
    int unite(int x, int y, int new_node) {
        x = find(x); y = find(y);
        if (x == y) return -1;
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        root[x] = new_node;   // 新 Kruskal 树节点成为合并后分量的根
        return new_node;
    }
    int get_root(int x) { return root[find(x)]; }
};

// 构建 Kruskal 重构树
// 返回：Kruskal 树的邻接表和节点值
// 叶节点 0..n-1 为原始顶点；节点 n..2n-2 为内部节点（MST 边）
void build_kruskal_tree(
        int n,
        vector<tuple<int,int,int>>& edges,   // {权重, u, v}——必须已排序
        vector<vector<int>>& ktree,          // ktree[node] = Kruskal 树中的子节点
        vector<int>& node_val                // node_val[node] = 边权（内部节点）或 0（叶节点）
) {
    ktree.assign(2 * n, {});
    node_val.assign(2 * n, 0);

    DSU dsu(n);
    int next_node = n;  // 下一个内部节点的 ID

    for (auto [w, u, v] : edges) {
        int ru = dsu.find(u), rv = dsu.find(v);
        if (ru == rv) continue;  // 同一分量，跳过

        // 创建新内部节点
        int x = next_node++;
        node_val[x] = w;

        // 添加子节点：u 和 v 所在分量的 Kruskal 树根
        ktree[x].push_back(dsu.get_root(u));
        ktree[x].push_back(dsu.get_root(v));

        dsu.unite(u, v, x);
    }
}

// 构建完毕后，在 ktree 上用倍增 LCA 回答瓶颈查询
// ktree 中的 lca(u, v) 即为 MST 上 u 和 v 之间的瓶颈边权

按权重排序边，用 DSU 应用 Kruskal 算法。输出 MST 的边权之和。

#include <bits/stdc++.h>
using namespace std;
// ...（使用 8.1.2 中的 Kruskal 模板）

Kruskal 算法结束后，检查 edges_added == n - 1。若不满足，图不连通。连通分量的数量为 dsu.components。

核心思路：查询 (u, v) 的答案就是 MST 上 u 到 v 路径中的最大边权。

构建 MST。对每个查询，在 MST 树上找路径并返回最大边。（朴素：对每个查询做 DFS/BFS，O(N·Q)。高效：LCA + 倍增，见第 8.4 章。）

竞赛中，若 Q ≤ 1000，朴素的 O(N·Q) 方案通常能通过。

这本质是在完全图上求 MST，但排序所有 O(N²) 条边太慢。核心观察：对于数轴上的点，MST 始终只使用相邻边！将奶牛按位置排序，只在相邻牧场之间添加边。

维护一个有序的边集合，增量运行 Kruskal 算法。当新增边 (u,v,w) 时：若 u 和 v 在当前 MST 中已连通，只有当 w 小于 MST 路径上的最大边权时，才用新边替换。

这需要找到树上路径中的最大边——使用欧拉游览 + 线段树，或倍增。

这不是 MST 问题——而是状压 DP 与最短路的结合。定义 dp[mask][v] = 以顶点 v 为节点、生成 mask 中所有顶点的最小代价树。