struct KruskalReconstructionTree { int n; // 原图节点数 int tot; // 重构树总节点数 vector> g; // 树邻接表 vector val; // 节点权值 (原节点 -1) vector parent; // 父节点 vector dsu; // 并查集 static const int LOG = 20; // 倍增 LCA 参数 vector depth; vector> 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> 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(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 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 res; collectLeaves(u, -1, res); return res; } // 从 s 出发,仅走边权 ≥ lim 的边能到达的所有节点(需降序构建) vector 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 res; collectLeaves(u, -1, res); return res; } // 收集子树中所有原图节点 void collectLeaves(int u, int p, vector &out) { if (u < n) { out.push_back(u); return; } for (int v : g[u]) if (v != p) collectLeaves(v, u, out); } };