Kruskal 重构树学习笔记

前言

我友圈里有这样一张图（其实不是友圈，就是某一个神秘入。

25 年 S 组复赛 T2 考了 MST，赛时没想到非原图 MST 的边不具竞争力，48pts 遗憾离场，看来是该恶补一下图论了。
知周所众，我的图论非常差劲（确信。

记录

Kruskal 重构树

什么是 Kruskal 重构树？

现在有一张图。

考虑 Kruskal 求 MST 的过程。

1. 先对每条边排序。
2. 从小到大枚举每条边，若该边连接的两点未连通，则将该边连通。

现在我们考虑在每次连边的过程中新开一个节点，该点左右子树为该边所连接的两个点（所在子树的祖先），同时新建的节点的点权为该边边权。

如图所示：

说明：
每个非叶子节点左上角数字即为点权。

这样建出来的树就是 Kruskal 重构树。

Kruskal 重构树有什么用？

下面是一些常用的性质。
::::info[一些性质]{open}
说明：下列性质都是按照边权降序排序后取边的顺序所构造的重构树的性质，若按边权升序（即正常求 MST 的枚举顺序），最大/最小值互换即可。

• 结论：对于一个非叶节点 $u$，其点权必然大于其所有祖先的点权。
  证明：若 $u$ 的一个祖先的点权大于 $u$ 的点权，则 $u$ 的祖先必然先被加入重构树，成为 $u$ 的子树，矛盾。
• 推论 $1$：对于两个叶节点 $u,v$，其在重构树上的简单路径中点权的最小值必然是两点 LCA 的点权。
  证明：两点 LCA 必然是两点简单路径深度最浅的节点。
• 推论 $2$：对于两个叶节点 $u,v$，其在原图上所有路径边权最小值的最大值必然是两个节点的 LCA 的点权。
  证明：若原图上存在一条路径边权的最小值比两点 LCA 的点权（由推论 $2$，该值即两点在树上的简单路径的最小值）更大，则那条边必然比两点 LCA 的点权那条边更早加入重构树，即那条边也应是重构树的一个非叶节点，矛盾。
  ::::

P1967 [NOIP 2013 提高组] 货车运输

由推论 $2$，建出重构树后求 LCA 即可。
:::success[100pts]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 10;
struct Node {
	int u, v, w;
	bool operator<(const Node &ppl)const & {
		return w > ppl.w;
	}
} e[maxn];
vector<int> E[maxn];
int val[maxn], fa[maxn], dep[maxn], f[maxn][22];
bool vis[maxn];
int n, m, q, cnt;
int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void dfs(int now, int fa) {
	vis[now] = 1, dep[now] = dep[fa] + 1, f[now][0] = fa;
	for (auto y : E[now]) if (y != fa) dfs(y, now);
	return;
}
int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	int d = dep[x] - dep[y];
	for (int i = 20; i >= 0; i--) if (d >> i & 1) x = f[x][i];
	if (x == y) return x;
	for (int i = 20; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
	sort(e + 1, e + m + 1);
	for (int i = 1; i <= n; i++) fa[i] = i;
	cnt = n;
	for (int i = 1; i <= m; i++) {
		int fu = find(e[i].u), fv = find(e[i].v), w = e[i].w;
		if (fu == fv) continue;
		val[++cnt] = w;
		fa[cnt] = fa[fu] = fa[fv] = cnt;
		E[cnt].push_back(fu), E[cnt].push_back(fv);
	}
	for (int i = cnt; i >= 1; i--) if (!vis[i]) dfs(i, 0);
	for (int j = 1; j <= 20; j++) for (int i = 1; i <= cnt; i++) f[i][j] = f[f[i][j - 1]][j - 1];
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		if (find(u) != find(v)) cout << "-1\n";
		else cout << val[LCA(u, v)] << "\n";
	}
	return 0;
}

:::
三倍经验：P2245，P9235。

P4768 [NOI2018] 归程

注意到问题可以转化为先求出所有可以通过海拔高于 $p$ 的边连通的点集，答案即为点集中所有点到 $1$ 的最小距离。

而后者可以先提前跑一遍 Dijkstra 预处理好每个点到 $1$ 的最小距离，前者就得用重构树。

当两个点能直接用汽车连通，必然满足两点之间存在一条边权最小值大于 $p$ 的路径，换而言之，若两点所有路径边权最小值的最大值大于 $p$，则一定存在一条这样的路径，也就是一定能直接用汽车连通（代价为 $0$）。
故我们考虑直接从 $v$ 开始往上慢慢跳，找到一个深度最浅的祖先节点，满足其点权仍大于 $p$，则所求点集即为其子树。
这一步可以用倍增加速。
::::info[略证]{}
不妨设该点为 $t$。

• 对于所有 $t$ 子树内的节点，由于两点之间简单路径的最小值（因为两点的 LCA 深度一定小于 $t$，所以至少是 $t$ 的点权，可能更大，不会更小）大于 $p$，故一定存在一条路径使得其所有边的海拔均大于 $p$，可以直接用汽车连通。
• 对于所有非 $t$ 子树内的节点，两点之间最短路径的最小值（两点 LCA 的深度一定大于 $t$，故该值一定小于 $t$ 的点权）必然不大于 $p$（若大于 $p$ 则 $t$ 能继续往上跳），一定无法用汽车连通。
  ::::
  点集求出来了，到 $1$ 的最小距离用一个简单的树形 DP 就可以实现了，每个点其子树到 $1$ 的最小距离就是其两个子节点到 $1$ 最小距离的最小值。
  ::::success[100pts]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int maxn = 4e5 + 10;
int T, n, m, Q, k, s;
struct Node {
	int v, l, a;
};
vector<Node>e[maxn];
int d[maxn], vis[maxn];
priority_queue<pii, vector<pii>, greater<pii>>q;
struct Edges {
	int u, v, l, a;
	bool operator<(const Edges &ppl)const & {
		return a > ppl.a;
	}
} E[maxn];
int cnt, fa[maxn], sonl[maxn], sonr[maxn], val[maxn];
int f[maxn][20];
int find(int x) {
	return (x == fa[x] ? x : fa[x] = find(fa[x]));
}
void initT() {
	for (int i = 1; i <= n; i++) e[i].clear();
	memset(d, 0x3f, sizeof d);
	memset(vis, 0, sizeof vis);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while (T--) {
		//cout << "----------" << T << "----------\n";
		initT();
		cin >> n >> m;
		for (int i = 1, u, v, l, a; i <= m; i++) {
			cin >> u >> v >> l >> a;
			e[u].push_back({v, l, a});
			e[v].push_back({u, l, a});
			E[i] = {u, v, l, a};
		}
		d[1] = 0;
		q.push({0, 1});
		while (!q.empty()) {
			auto [_, u] = q.top();
			q.pop();
			if (vis[u]) continue;
			vis[u] = 1;
			for (auto [v, l, a] : e[u]) {
				int w = l;
				if (d[v] <= d[u] + w) continue;
				d[v] = d[u] + w;
				q.push({d[v], v});
			}
		}
		//for (int i = 1; i <= n; i++) cout << d[i] << " ";
		//cout << "\n";
		//continue;
		sort(E + 1, E + m + 1);
		cnt = n;
		for (int i = 1; i <= n; i++) fa[i] = i;
		for (int i = 1; i <= m; i++) {
			int fu = find(E[i].u), fv = find(E[i].v), w = E[i].a;
			if (fu == fv) continue;
			val[++cnt] = w;
			fa[fu] = fa[fv] = fa[cnt] = cnt;
			sonl[cnt] = fu, sonr[cnt] = fv;
			f[fu][0] = f[fv][0] = cnt;
		}
		for (int i = n + 1; i <= cnt; i++) d[i] = min(d[sonl[i]], d[sonr[i]]);
		for (int i = 1; i <= 19; i++) for (int j = 1; j <= cnt; j++) f[j][i] = f[f[j][i - 1]][i - 1];
		//cout << cnt << "\n";
		//for (int i = cnt; i > n; i--) cout << i << " " << sonl[i] << " " << sonr[i] << " " << dep[i] << " " << val[i] << "\n";
		//continue;
		cin >> Q >> k >> s;
		int lastans = 0;
		while (Q--) {
			int V, P;
			cin >> V >> P;
			V = (V + k * lastans - 1) % n + 1, P = (P + k * lastans) % (s + 1);
			int now = V;
			for (int i = 19; i >= 0; i--) {
				if (val[f[now][i]] <= P) continue;
				now = f[now][i];
			}
			cout << d[now] << "\n";
			lastans = d[now];
		}
		//cout << "\n\n";
	}
	return 0;
}

::::

P4899 [IOI 2018] werewolf 狼人

很显然对于每一个询问我们要求出从 $S$ 开始人形所能到达的点集，从 $E$ 开始狼形所能到达的点集，查有无交。

求两个点集可以用两颗 Kruskal 重构树解决，边权恰好为两点的最小值和最大值。

求交的话考虑用时间戳对每一个点的子树所包含的范围变为一个区间，然后扫描线离线处理一下就行了。
::::success[100pts]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 10;
int n, m, q;
int fa[maxn];
int find(int x) {
	return (x == fa[x] ? x : fa[x] = find(fa[x]));
}
namespace Emin {
	struct Edge {
		int u, v, w;
		bool operator<(const Edge &ppl) const {
			return w > ppl.w;
		}
	} e[maxn];
	int cnt, val[maxn], dfn[maxn], sz[maxn], tot;
	int f[maxn][20];
	vector<int> G[maxn];
	void dfs(int u) {
		dfn[u] = ++tot;
		sz[u] = 1;
		for (int v : G[u]) {
			dfs(v);
			sz[u] += sz[v];
		}
	}
	void init() {
		cnt = n;
		sort(e + 1, e + m + 1);
		for (int i = 1; i <= n; i++) fa[i] = i;
		for (int i = 1; i <= m; i++) {
			int fu = find(e[i].u), fv = find(e[i].v);
			if (fu == fv) continue;
			val[++cnt] = e[i].w;
			fa[fu] = fa[fv] = fa[cnt] = cnt;
			f[fu][0] = f[fv][0] = cnt;
			G[cnt].push_back(fu), G[cnt].push_back(fv);
		}
		for (int i = cnt; i >= 1; i--) if (!dfn[i]) dfs(i);
		for (int k = 1; k <= 19; k++) for (int i = 1; i <= cnt; i++) f[i][k] = f[f[i][k - 1]][k - 1];
	}
	int jump(int x, int L) {
		for (int i = 19; i >= 0; i--) {
			if (!f[x][i] || val[f[x][i]] < L) continue;
			x = f[x][i];
		}
		return x;
	}
}
namespace Emax {
	struct Edge {
		int u, v, w;
		bool operator<(const Edge &ppl) const {
			return w < ppl.w;
		}
	} e[maxn];
	int cnt, val[maxn], dfn[maxn], sz[maxn], tot;
	int f[maxn][20];
	vector<int> G[maxn];
	void dfs(int u) {
		dfn[u] = ++tot;
		sz[u] = 1;
		for (int v : G[u]) {
			dfs(v);
			sz[u] += sz[v];
		}
	}
	void init() {
		cnt = n;
		sort(e + 1, e + m + 1);
		for (int i = 1; i <= n; i++) fa[i] = i;
		for (int i = 1; i <= m; i++) {
			int fu = find(e[i].u), fv = find(e[i].v);
			if (fu == fv) continue;
			val[++cnt] = e[i].w;
			fa[fu] = fa[fv] = fa[cnt] = cnt;
			f[fu][0] = f[fv][0] = cnt;
			G[cnt].push_back(fu), G[cnt].push_back(fv);
		}
		for (int i = cnt; i >= 1; i--) if (!dfn[i]) dfs(i);
		for (int k = 1; k <= 19; k++) for (int i = 1; i <= cnt; i++) f[i][k] = f[f[i][k - 1]][k - 1];
	}
	int jump(int x, int R) {
		for (int i = 19; i >= 0; i--) {
			if (!f[x][i] || val[f[x][i]] > R) continue;
			x = f[x][i];
		}
		return x;
	}
}
namespace BitTree {
	struct Tree {
		int c[maxn];
		void add(int x, int v) {
			for (; x <= Emax::tot; x += x & -x) c[x] += v;
		}
		int sum(int x) {
			int res = 0;
			for (; x; x -= x & -x) res += c[x];
			return res;
		}
		int query(int l, int r) {
			return sum(r) - sum(l - 1);
		}
	};
}
using namespace BitTree;
Tree T;
struct Query {
	int pos, id, l, r, sign;
};
vector<Query> Q[maxn];
int ans[maxn];
int Id[maxn];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		u++, v++;
		Emin::e[i] = {u, v, min(u, v)};
		Emax::e[i] = {u, v, max(u, v)};
	}
	Emin::init(), Emax::init();
	for (int i = 1; i <= n; i++) Id[Emin::dfn[i]] = Emax::dfn[i];
	for (int i = 1; i <= q; i++) {
		int S, E, L, R;
		cin >> S >> E >> L >> R;
		S++, E++, L++, R++;
		int nows = Emin::jump(S, L), nowe = Emax::jump(E, R);
		int l1 = Emin::dfn[nows], r1 = l1 + Emin::sz[nows] - 1,
		    l2 = Emax::dfn[nowe], r2 = l2 + Emax::sz[nowe] - 1;
		Q[r1].push_back({r1, i, l2, r2, 1});
		Q[l1 - 1].push_back({l1 - 1, i, l2, r2, -1});
	}
	for (int i = 1; i <= Emin::tot; i++) {
		if (Id[i]) T.add(Id[i], 1);
		for (auto q : Q[i]) {
			int cnt = T.query(q.l, q.r);
			ans[q.id] += q.sign * cnt;
		}
	}
	for (int i = 1; i <= q; i++) cout << (ans[i] ? 1 : 0) << "\n";
	return 0;
}

::::

P7834 [ONTAK2010] Peaks 加强版

“困难值小于等于 $x$”这个东西显然可以用 Kruskal 重构树，往上调到一个深度最浅的且点权不大于 $x$ 的点，那么该点的子树内的所有叶子节点都是可以随便走的，非该点子树内的所有叶节点一定是走不到的。

注意到子树内所有叶节点的时间戳是连续的，所以问题转化为求一个区间的第 $k$ 大值，套一个主席树即可。
::::success[100pts]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5e5 + 10;
int n, m, q, h[maxn];
namespace Kruskal_Tree {
	int fa[maxn];
	int find(int x) {
		return (x == fa[x] ? x : fa[x] = find(fa[x]));
	}
	struct Edge {
		int u, v, w;
		bool operator<(const Edge &ppl) const {
			return w < ppl.w;
		}
	} e[maxn];
	int cnt, val[maxn], sonl[maxn], sonr[maxn], dfn[maxn], tot, a[maxn], L[maxn], R[maxn];
	int f[maxn][20];
	void dfs(int u) {
		if (sonl[u]) dfs(sonl[u]);
		if (sonr[u]) dfs(sonr[u]);
		if (u <= n) {
			dfn[u] = ++tot;
			a[tot] = h[u];
			L[u] = R[u] = tot;
		} else {
			L[u] = min(L[sonl[u]], L[sonr[u]]);
			R[u] = max(R[sonl[u]], R[sonr[u]]);
		}
	}
	void init() {
		cnt = n;
		sort(e + 1, e + m + 1);
		for (int i = 1; i <= 2 * n; i++) fa[i] = i;
		for (int i = 1; i <= m; i++) {
			int fu = find(e[i].u), fv = find(e[i].v);
			if (fu == fv) continue;
			val[++cnt] = e[i].w;
			fa[fu] = fa[fv] = fa[cnt] = cnt;
			f[fu][0] = f[fv][0] = cnt;
			sonl[cnt] = fu, sonr[cnt] = fv;
		}
		dfs(cnt);
		for (int k = 1; k <= 19; k++) for (int i = 1; i <= cnt; i++) f[i][k] = f[f[i][k - 1]][k - 1];
	}
	int jump(int x, int H) {
		for (int i = 19; i >= 0; i--) {
			if (!f[x][i] || val[f[x][i]] > H) continue;
			x = f[x][i];
		}
		return x;
	}
}
using namespace Kruskal_Tree;
struct PresidentTree {
	int ls[maxn * 20], rs[maxn * 20], sum[maxn * 20], rt[maxn], tot;
	void build(int &p, int l, int r) {
		p = ++tot;
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(ls[p], l, mid);
		build(rs[p], mid + 1, r);
	}
	void update(int &p, int pre, int l, int r, int x) {
		p = ++tot;
		ls[p] = ls[pre], rs[p] = rs[pre], sum[p] = sum[pre] + 1;
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (x <= mid) update(ls[p], ls[pre], l, mid, x);
		else update(rs[p], rs[pre], mid + 1, r, x);
	}
	int query(int u, int v, int l, int r, int k) {
		if (l == r) return l;
		int mid = (l + r) >> 1;
		int s = sum[rs[v]] - sum[rs[u]];
		if (k <= s) return query(rs[u], rs[v], mid + 1, r, k);
		else return query(ls[u], ls[v], l, mid, k - s);
	}
} T;
vector<int> ans;
int getid(int x) {
	return lower_bound(ans.begin(), ans.end(), x) - ans.begin() + 1;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		cin >> h[i];
		ans.push_back(h[i]);
	}
	for (int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		e[i] = {u, v, w};
	}
	init();
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	int N = ans.size();
	T.build(T.rt[0], 1, N);
	for (int i = 1; i <= n; i++) T.update(T.rt[i], T.rt[i - 1], 1, N, getid(a[i]));
	int lastans = 0;
	while (q--) {
		int v, x, k;
		cin >> v >> x >> k;
		v = (v ^ lastans) % n + 1, x = x ^ lastans, k = (k ^ lastans) % n + 1;
		int tmp = jump(v, x);
		int l = L[tmp], r = R[tmp];
		if (r - l + 1 < k) cout << "-1\n", lastans = 0;
		else {
			int id = T.query(T.rt[l - 1], T.rt[r], 1, N, k);
			cout << (lastans = ans[id - 1]) << "\n";
		}
	}
	return 0;
}

::::
双倍经验：P4197。

P13548 [OOI 2022] Air Reform

这真是神仙题了。爆肝我 8days，看来还是太菜了。

大概转化一下题意：就是说给你一张无向连通图，你需要建它的一个补图，其中补图两点的边权就是在原图中两点最小瓶颈路的最大边权，你需要求出对于原图的每条边 $(u,v)$，求两点在补图中最小瓶颈路的最大边权。

对于最小瓶颈路的最大边权，这个东西显然可以用 Kruskal 重构树解决，求一个 LCA 即可。
所以算法瓶颈在于怎么快速建出补图的重构树。

考虑暴力，注意到在建原图的重构树时是从小到大枚举边权建新节点的，所以我们考虑在每次建新节点的时候枚举左右两个子树集合，若两点在原图中没有边且在补图中还未连通，则连一条边。
可以得到 21pts 的高分。
::::warning[21pts]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int maxn = 3e5 + 10;
int T, g, n, m, q, cnt;
struct Node {
	int u, v, w;
	bool operator<(const Node &ppl)const & {
		return w < ppl.w;
	}
} e[maxn], _[maxn];
int val[maxn], f[maxn][21], dep[maxn];
vector<int>son[maxn];
map<pii, int>mp;
struct dsu {
	int fa[maxn];
	void init(int n) {
		for (int i = 1; i <= n; i++) fa[i] = i;
	}
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);
	}
} B1, B2;
int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	int d = dep[x] - dep[y];
	for (int i = 20; i >= 0; i--) if (d >> i & 1) x = f[x][i];
	if (x == y) return x;
	for (int i = 20; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
void init() {
	mp.clear();
	for (int i = 1; i <= n; i++) son[i].clear();
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> T >> g;
	while (T--) {
		init();
		cin >> n >> m;
		for (int i = 1, u, v, w; i <= m; i++) {
			cin >> u >> v >> w;
			mp[ {u, v}] = mp[ {v, u}] = 1;
			_[i] = e[i] = {u, v, w};
		}
		sort(e + 1, e + m + 1);
		for (int i = 1; i <= n; i++) son[i].push_back(i);
		B1.init(n), B2.init(n);
		int _cnt = n;
		cnt = n;
		for (int i = 1; i <= m; i++) {
			int fu = B1.find(e[i].u), fv = B1.find(e[i].v), w = e[i].w;
			if (fu == fv) continue;
			_cnt++;
			B1.fa[_cnt] = B1.fa[fu] = B1.fa[fv] = _cnt;
			for (auto x : son[fu]) for (auto y : son[fv]) {//暴力枚举左右子树 
					if (mp[ {x, y}]) continue;
					int fx = B2.find(x), fy = B2.find(y);
					if (fx == fy) continue;
					val[++cnt] = w;
					f[fx][0] = f[fy][0] = cnt;
					B2.fa[cnt] = B2.fa[fx] = B2.fa[fy] = cnt;
				}
			son[_cnt].clear();
			for (auto x : son[fu]) son[_cnt].push_back(x);
			for (auto x : son[fv]) son[_cnt].push_back(x);
			son[fu].clear(), son[fv].clear();
		}
		for (int k = 1; k <= 20; k++) for (int i = 1; i <= cnt; i++) f[i][k] = f[f[i][k - 1]][k - 1];
		dep[cnt] = 1;
		for (int i = cnt - 1; i >= 1; i--) dep[i] = dep[f[i][0]] + 1;
		for (int i = 1; i <= m; i++) {
			int u = _[i].u, v = _[i].v;//查原图的边 
			cout << val[LCA(u, v)] << " ";
		}
		cout << "\n";
	}
	return 0;
}

::::
考虑优化。

为了方便表示，对于当前节点 $u$，不妨设其左右子树分别含 $id_l$ 和 $id_r$ 个联通块，$st_x$ 表示第 $x$ 个连通块中的元素个数。

考虑如何合并 $u$ 左右子树的连通块。

不妨先枚举左右子树的连通块 $id_l$ 和 $id_r$，用 $idx$ 和 $idy$ 表示，再枚举每个连通块中间的元素 $st_{idx}$ 和 $st_{idy}$，用 $x$ 和 $y$ 表示，若两点在原图中没有边，且在补图中尚未连通，则将两点相连（到这里和暴力是一样的）。
$x$ 和 $y$ 连边后，考虑将 $st_{idy}$ 从 $id_r$ 中删去，加到 $st_{idx}$ 里去。

这样会存在一个问题，若左子树 $id_l$ 内有两个连通块 $idx$ 和 $idz$ 内均有节点能和 $idy$ 连通块内的节点相连，则会导致这三个连通块合并成一个大的连通块。
但我们若将 $st_{idy}$ 和 $st_{idx}$ 联通后直接将其加入 $st_{idx}$，就会导致建出的树不是标准的重构树，或是建不出一个完整的树。
所以当我们处理完 $st_{idx}$ 内的所有节点后，还要将 $st_{idx}$ 加到 $id_r$ 里去。

然后在做一个启发式合并，复杂度就会变成优秀的 $O(n\log^2n)$

正确性显然，考虑证明时间复杂度。

• 若 $st_{idx}$ 和 $st_{idy}$ 存在点对使得两连通块连通。显然最多只会连通 $n$ 次（在补图中判连通还要乘一个 $\alpha(n)$），每一次联通后把两个块启发式合并，这一部分复杂度是 $O(\alpha(n)\log n)$ 的。
• 若不能连通，则枚举完 $st_{idy}$ 后，会将 $st_{idx}$ 加到 $id_r$ 里，注意到这里也是用启发式合并的，一个点最多会被加入 $\log n$ 次。

同时每次查一下在原图是否有边也是 $\log n$ 的。
所以建补图重构树的复杂度是 $O(m\log^2n+m\alpha(n)\log n)$。

其余部分复杂度显然没有建补图的复杂度大，直接忽视即可。
::::success[100pts]

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 4e5 + 10;
int T, g, n, m;
int ans[maxn];
set<int> E[maxn], id[maxn], st[maxn];
struct Edge {
	int u, v, w;
	bool operator<(const Edge &ppl) const {
		return w < ppl.w;
	}
} e[maxn], _[maxn];
namespace Kurskal_Tree {
	struct dsu {
		int fa[maxn];
		void init(int n) {
			for (int i = 1; i <= n; i++) fa[i] = i;
		}
		int find(int x) {
			return fa[x] == x ? x : fa[x] = find(fa[x]);
		}
	} B1, B2;
	struct Tree2 {
		int cnt, val[maxn], f[maxn][30], dep[maxn];
		void add(int u, int v, int w) {
			int fu = B2.find(u), fv = B2.find(v);
			if (fu == fv) return;
			val[++cnt] = w;
			f[fu][0] = f[fv][0] = cnt;
			B2.fa[fu] = B2.fa[fv] = B2.fa[cnt] = cnt;
		}
		void init() {
			dep[cnt] = 1;
			for (int i = cnt; i >= 1; i--) dep[i] = dep[f[i][0]] + 1;
			for (int k = 1; k <= 20; k++) for (int i = 1; i <= cnt; i++) f[i][k] = f[f[i][k - 1]][k - 1];
		}
		int LCA(int x, int y) {
			if (dep[x] < dep[y]) swap(x, y);
			int d = dep[x] - dep[y];
			for (int i = 20; i >= 0; i--) if (d >> i & 1) x = f[x][i];
			if (x == y) return x;
			for (int i = 20; i >= 0; i--) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
			return f[x][0];
		}
	} T2;
	struct Tree1 {
		int cnt, sz[maxn];
		void init() {
			cnt = n, T2.cnt = n;
			sort(e + 1, e + m + 1);
			B1.init(n), B2.init(n);
			for (int i = 1; i <= n; i++) sz[i] = 1, id[i].insert(i), st[i].insert(i);
			for (int i = 1; i <= m; i++) {
				int fu = B1.find(e[i].u), fv = B1.find(e[i].v), w = e[i].w;
				if (fu == fv) continue;
				++cnt;
				B1.fa[fu] = B1.fa[fv] = B1.fa[cnt] = cnt;
				int u = cnt, l = fu, r = fv;
				sz[u] = sz[l] + sz[r];
				if (sz[l] > sz[r]) swap(l, r);//启发式合并 
				for (auto idx : id[l]) {
					auto it = id[r].begin();
					while (it != id[r].end()) {
						auto idy = *it;
						bool flag = 0;
						for (auto x : st[idx]) {
							for (auto y : st[idy]) if (E[x].find(y) == E[x].end()) {
									flag = 1;
									T2.add(x, y, w);//能连通直接连 
									break;
								}
							if (flag) break;
						}
						if (flag) {
							if (st[idx].size() < st[idy].size()) swap(st[idx], st[idy]);//启发式合并 
							for (auto y : st[idy]) st[idx].insert(y);
							st[idy].clear();
							it = id[r].erase(it); 
						} else ++it;
					}
					id[r].insert(idx);
				}
				id[u] = id[r];//所有连通块都加到id[r]里了，直接赋值给id[u]即可 
			}
		}
	} T1;
}
using namespace Kurskal_Tree;
void init() {
	for (int i = 1; i <= n * 2; i++) st[i].clear(), E[i].clear(), id[i].clear();
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> g;
	while (T--) {
		cin >> n >> m;
		init();
		for (int i = 1, u, v, w; i <= m; i++) {
			cin >> u >> v >> w;
			_[i] = e[i] = {u, v, w};
			E[u].insert(v), E[v].insert(u);
		}
		T1.init(), T2.init();
		for (int i = 1; i <= m; i++) {
			int u = _[i].u, v = _[i].v;
			cout << T2.val[T2.LCA(u, v)] << " ";
		}
		cout << "\n";
	}
	return 0;
}

::::