灵异事件代码喜旧厌新

#include <bits/stdc++.h>
using namespace std;

const int N = 20050, M = 50050; 
int n, m , val[N] , fa[N];
vector<int> G[N];
struct road{
    int u , v ,w;  
}ro[M];

int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}

bool cmp(road a , road b) {
    return a.w > b.w;
}

void kru() {
    for(int i = 1;i <= n;i++)
        fa[i] = i;
    sort(ro + 1 , ro + m + 1 , cmp);
    
    for(int i = 1;i <= m;i++) {
        int fu = find(ro[i].u), fv = find(ro[i].v);
        if(fu == fv) continue;
        
        fa[++n] = n;
        val[n] = ro[i].w;
        G[n].push_back(fu);
        G[n].push_back(fv);
        fa[fu] = n;
        fa[fv] = n;
    }
}

int dep[N] , lc[N][30];
void dfs(int u,int fa) {
    dep[u] = dep[fa] + 1;
    lc[u][0] = fa;
    for(int i = 1;i <= 20;i++)
        lc[u][i] = lc[lc[u][i-1]][i-1];
    for(int i : G[u]) {
        if(i != fa)
            dfs(i , u);
    }       
}

int lca(int x , int y) {
    if(dep[x] < dep[y])
        swap(x , y);
    for(int i = 20;i >= 0;i--)
        if(dep[lc[x][i]] >= dep[y])
            x = lc[x][i];
    if(x == y)
        return x;
    for(int i = 20;i >= 0;i--)
        if(lc[x][i] != lc[y][i])
            x = lc[x][i] , y = lc[y][i];
    return lc[x][0];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i =1;i <= m;i++) {
        cin >> ro[i].u >> ro[i].v >> ro[i].w;
    }
    
    kru();
    
    for(int i = 1; i <= n; i ++)
        if(find(i) == i) dfs(i, 0);
    
    int q; cin >> q;
    while(q --) {
        int x, y; cin >> x >> y;
        if(find(x) == find(y)) 
            cout << val[lca(x, y)] << '\n';
        else 
            cout << "-1" << '\n';
    }
    
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 5e4 + 10;
int n, m, u[M], v[M], w[M];

int fa[N], val[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]); }

vector<int> G[N];

void Kruskal() {
	for(int i = 1; i <= n; i ++)
		fa[i] = i;
	vector<int> vec(m);
	iota(vec.begin(), vec.end(), 1);
	sort(vec.begin(), vec.end(), [](int x, int y) {
		return w[x] > w[y];
	});
	for(int i : vec) {
		if(find(u[i]) == find(v[i])) continue;
		val[++n] = w[i]; fa[n] = n;
		G[n].push_back(find(u[i])), G[n].push_back(find(v[i]));
		fa[find(u[i])] = fa[find(v[i])] = n;
	}
}

int anc[N][21], dep[N];
void dfs(int u, int fa) {
	anc[u][0] = fa, dep[u] = dep[fa] + 1;
	for(int i = 1; i <= 20; i ++)
		anc[u][i] = anc[anc[u][i - 1]][i - 1];
	for(int v : G[u])
		dfs(v, u);
}
int lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 20; i >= 0; i --)
		if(dep[anc[x][i]] >= dep[y]) 
			x = anc[x][i];
	if(x == y) return x;
	for(int i = 20; i >= 0; i --)
		if(anc[x][i] != anc[y][i])
			x = anc[x][i], y = anc[y][i];
	return anc[x][0];
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
		cin >> u[i] >> v[i] >> w[i];
	Kruskal();
	
	for(int i = 1; i <= n; i ++)
		if(find(i) == i) dfs(i, 0);
	
	int q; cin >> q;
	while(q --) {
		int x, y; cin >> x >> y;
		if(find(x) == find(y)) cout << val[lca(x, y)] << '\n';
		else cout << "-1" << '\n';
	}
	
	return 0;
}