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);
}
};