//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "Kruskal 重构树": {
        "prefix": "acm-4.4KruskalReconstructionTree",
        "body": [
            "struct KruskalReconstructionTree {",
            "    int n;                      // 原图节点数",
            "    int tot;                    // 重构树总节点数",
            "    vector<vector<int>> g;      // 树邻接表",
            "    vector<int> val;            // 节点权值 (原节点 -1)",
            "    vector<int> parent;         // 父节点",
            "    vector<int> dsu;            // 并查集",
            "",
            "    static const int LOG = 20;  // 倍增 LCA 参数",
            "    vector<int> depth;",
            "    vector<vector<int>> up;",
            "",
            "    KruskalReconstructionTree(int n_) : n(n_) {",
            "        tot = n;",
            "        g.resize(2 * n);",
            "        val.resize(2 * n);",
            "        parent.assign(2 * n, -1);",
            "        dsu.resize(2 * n);",
            "        iota(dsu.begin(), dsu.end(), 0);",
            "        for (int i = 0; i < n; i++) val[i] = -1;",
            "        depth.resize(2 * n);",
            "    }",
            "",
            "    int find(int x) {",
            "        while (dsu[x] != x) dsu[x] = dsu[dsu[x]], x = dsu[x];",
            "        return x;",
            "    }",
            "",
            "    // 构建重构树。edges: {u,v,w}",
            "    void build(vector<tuple<int, int, int>> edges, bool sorted = false) {",
            "        if (!sorted) {",
            "            sort(edges.begin(), edges.end(),",
            "                 [](const auto &a, const auto &b) {",
            "                     return get<2>(a) > get<2>(b); // 最大瓶颈路",
            "                 });",
            "        }",
            "        for (auto &[u, v, w] : edges) {",
            "            int ru = find(u), rv = find(v);",
            "            if (ru == rv) continue;",
            "            int node = tot++;",
            "            val[node] = w;",
            "            g[node].push_back(ru);",
            "            g[node].push_back(rv);",
            "            parent[ru] = parent[rv] = node;",
            "            dsu[ru] = dsu[rv] = node;",
            "            dsu[node] = node;",
            "            if (tot >= (int)g.size()) {",
            "                g.resize(tot + 5);",
            "                val.resize(tot + 5);",
            "                parent.resize(tot + 5);",
            "                depth.resize(tot + 5);",
            "            }",
            "        }",
            "        g.resize(tot);",
            "        val.resize(tot);",
            "        parent.resize(tot);",
            "        // 建立倍增表",
            "        initLCA();",
            "    }",
            "",
            "    void initLCA() {",
            "        depth.assign(tot, 0);",
            "        up.assign(tot, vector<int>(LOG, -1));",
            "        for (int i = 0; i < tot; i++)",
            "            if (parent[i] == -1) dfs(i, -1);",
            "    }",
            "",
            "    void dfs(int u, int p) {",
            "        up[u][0] = p;",
            "        for (int j = 1; j < LOG; j++) {",
            "            if (up[u][j - 1] != -1)",
            "                up[u][j] = up[up[u][j - 1]][j - 1];",
            "            else",
            "                up[u][j] = -1;",
            "        }",
            "        for (int v : g[u]) {",
            "            if (v == p) continue;",
            "            depth[v] = depth[u] + 1;",
            "            dfs(v, u);",
            "        }",
            "    }",
            "",
            "    // 查询 u, v 的 LCA",
            "    int lca(int u, int v) {",
            "        if (depth[u] < depth[v]) swap(u, v);",
            "        int diff = depth[u] - depth[v];",
            "        for (int j = 0; j < LOG; j++) {",
            "            if (diff >> j & 1) u = up[u][j];",
            "        }",
            "        if (u == v) return u;",
            "        for (int j = LOG - 1; j >= 0; j--) {",
            "            if (up[u][j] != up[v][j]) {",
            "                u = up[u][j];",
            "                v = up[v][j];",
            "            }",
            "        }",
            "        return up[u][0];",
            "    }",
            "",
            "    // 查询原图 u->v 瓶颈路（最小边权的最大值）",
            "    int queryMaxEdgeMin(int u, int v) {",
            "        int w = lca(u, v);",
            "        if (w == -1) return -1;",
            "        return val[w];",
            "    }",
            "",
            "    // 从 s 出发，仅走边权 ≤ lim 的边能到达的所有节点",
            "    vector<int> queryReachable(int s, int lim) {",
            "        int u = s;",
            "        for (int j = LOG - 1; j >= 0; j--)",
            "            if (up[u][j] != -1 && val[up[u][j]] <= lim)",
            "                u = up[u][j];",
            "        vector<int> res;",
            "        collectLeaves(u, -1, res);",
            "        return res;",
            "    }",
            "",
            "    // 从 s 出发，仅走边权 ≥ lim 的边能到达的所有节点（需降序构建）",
            "    vector<int> queryReachableMin(int s, int lim) {",
            "        int u = s;",
            "        for (int j = LOG - 1; j >= 0; j--)",
            "            if (up[u][j] != -1 && val[up[u][j]] >= lim)",
            "                u = up[u][j];",
            "        vector<int> res;",
            "        collectLeaves(u, -1, res);",
            "        return res;",
            "    }",
            "",
            "    // 收集子树中所有原图节点",
            "    void collectLeaves(int u, int p, vector<int> &out) {",
            "        if (u < n) { out.push_back(u); return; }",
            "        for (int v : g[u]) if (v != p) collectLeaves(v, u, out);",
            "    }",
            "};"
        ],
        "description": "插入 Kruskal 重构树"
    }
}