正瑞讲的原题我写写代码

可持久化并查集+整体二分

写可持久化并查集的时候一定小心我们不能合并原本就在一个连通块内的...同时回溯不能回溯过头了

写的不是很好,应该先递归右边的...再消除影响递归左边

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;

int n, m, q, tot;
struct rec {
	int x, y, z, id;
	bool operator<(const rec &w)const {
		return x < w.x;
	}
} a[MAXN], e[MAXN], b1[MAXN], b2[MAXN], qp[MAXN];

int ans[MAXN], siz[MAXN], f[MAXN];

inline int getf(int x) {
	while(x != f[x])x = f[x];
	return x;
}

inline void merge(int x, int y) {
	int u = getf(x);
	int v = getf(y);
	qp[++tot].x = u;
	qp[tot].y = f[u];//还原这个玩意
	qp[tot].z = siz[u];
	qp[++tot].x = v;
	qp[tot].y = f[v];
	qp[tot].z = siz[v];
	if(u == v)return ;
	if(siz[u] > siz[v]) {
		siz[u] += siz[v];
		f[v] = u;
	} else {
		siz[v] += siz[u];
		f[u] = v;
	}
	return ;
}


inline void goback() {
	f[qp[tot].x] = qp[tot].y;
	siz[getf(qp[tot].x)] = qp[tot].z;
	--tot;
	f[qp[tot].x] = qp[tot].y;
	siz[getf(qp[tot].x)] = qp[tot].z;
	--tot;
}

inline void solve(int l, int r, int L, int R) {
	if(l == r) {
		for(int i = L; i <= R; ++i)ans[a[i].id] = l;
		return ;
	}
	int mid = (l + r) >> 1;
	for(int i = l; i <= mid; ++i)
		merge(e[i].x, e[i].y);
	int t1 = 0, t2 = 0;
	for(int i = L; i <= R; ++i) {
		int np = getf(a[i].x) == getf(a[i].y) ? siz[getf(a[i].x)] : (siz[getf(a[i].x)] + siz[getf(a[i].y)]);
		if(np >= a[i].z) {
			b1[++t1] = a[i];
		} else b2[++t2] = a[i];
	}
	for(int i = l; i <= mid; ++i)
		goback();//回溯即可
	for(int i = 1; i <= t1; ++i)a[i + L - 1] = b1[i];
	for(int i = 1; i <= t2; ++i)a[i + L - 1 + t1] = b2[i];
	if(t1)solve(l, mid, L, L + t1 - 1);
	if(t2) {
		for(int i = l; i <= mid; ++i)
			merge(e[i].x, e[i].y);
		solve(mid + 1, r, L + t1, R);
		for(int i = l; i <= mid; ++i)
			goback();//回溯即可
	}
	return ;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &e[i].x, &e[i].y);
	}
	for(int i = 1; i <= n; ++i)f[i] = i, siz[i] = 1;
	scanf("%d", &q);
	for(int i = 1; i <= q; ++i) {
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
		a[i].id = i;
	}
	solve(1, m, 1, q);
	for(int i = 1; i <= q; ++i)printf("%d\n", ans[i]);
	return 0;
}

还有克鲁斯卡尔重构树做法

用二分,然后倍增,因为越靠上点权越大,所以我们x,y一起倍增,知道找到第一个siz和大于z的位置即可