rt，评测记录

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
	int b, e, w;//begin,end
}a[50005];
int fa[10005], head[10005], to[10005], nxt[10005], c[10005], tot, st[20][10005], dep[10005], f[20][10005], vis[10005];//st：权值，f：跳跃 
int n, m, sum = 0;
bool cmp(node x, node y){
	return x.w > y.w;
}
int find(int x){
	if(fa[x] == x)return x;
	return fa[x] = find(fa[x]);
}

void add(int u, int v, int w){
	nxt[++tot] = head[u];
	head[u] = tot;
	to[tot] = v;
	c[tot] = w;
}

void kruskal(){
	for(int i = 1;i <= m;i++){
		if(find(a[i].b) != find(a[i].e)){
			fa[find(a[i].b)] = find(a[i].e);
			sum += a[i].w;
			add(a[i].b, a[i].e, a[i].w);
			add(a[i].e, a[i].b, a[i].w);
		}
	}
}
void dfs(int pos, int fa){
	vis[pos] = 1;
	dep[pos] = dep[fa] + 1;
	f[0][pos] = fa;
	for(int i = head[pos];i;i = nxt[i]){
		if(to[i] == fa)continue;
		st[0][to[i]] = c[i];
		dfs(to[i], pos);
	}
}

int lca(int u, int v){
	int res = 1000000000;
	if(find(u) != find(v))return -1; 
	if (dep[u] < dep[v])
		swap(u, v);
	int t = dep[u] - dep[v];
	for (int i = 19; i >= 0; i--) {
		if ((t >> i ) & 1){
			res = min(res, st[i][u]);
			u = f[i][u];
		}
	}
	if (u == v)
		return res;
	for (int i = 19; i >= 0; i--) {
		if (f[i][u] != f[i][v]) {
			res = min(res, st[i][u]);
			u = f[i][u];
			v = f[i][v];
		}
	}
	res = min(res, min(st[0][u], st[0][v]));
	return res;
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> a[i].b >> a[i].e >> a[i].w;
	}
	for(int i = 1;i <= n;i++){
		fa[i] = i;
	}
	sort(a + 1, a + m + 1, cmp);
	kruskal();
	for(int i = 1;i <= n;i++){
		if(!vis[i]){
			dfs(i, i);
			st[0][i] = 1000000000;
		}
	} 
	for(int k = 1;(1 << k) <= n;k++){
		for(int i = 1;i <= n;i++){
			f[k][i] = f[k - 1][f[k - 1][i]];
			st[k][i] = min(st[k - 1][i], st[k - 1][f[k - 1][i]]);
		}
	}
	int q;
	cin >> q;
	while(q--){
		int a, b;
		cin >> a >> b;
		cout << lca(a, b) << "\n";
	}
	return 0;
} ```