Kruskal重构树求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 15;
inline int read() {
    int x = 0, f = 0;
    char c = getchar();
    while (!isdigit(c)) {
        f |= c == '-';
        c = getchar();
    }
    while (isdigit(c)) {
        x = x * 10 + (c ^ 48);
        c = getchar();
    }
    return f ? -x : x;
}
struct node{
	int u,v,w;
}e[N<<2];
struct line{
	int v,nxt;
}E[N<<2];
int f[N],n,m,val[N],tot,h[N],fa[N],dep[N],siz[N],wg[N],top[N],vis[N],ff[N];
void dfs1(int u,int f){
	fa[u]=f;
	dep[u]=dep[f]+1;
	siz[u]=1;
	vis[u]=1;
	for(int i=h[u];i;i=E[i].nxt){
		int v=E[i].v;
		if(v==f)continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[wg[u]]<siz[v])wg[u]=v;
	}
}
void dfs2(int u,int Top){
	top[u]=Top;
	if(wg[u]){
		dfs2(wg[u],Top);
		for(int i=h[u];i;i=E[i].nxt){
			int v=E[i].v;
			if(v==fa[u]||v==wg[u])continue;
			dfs2(v,v);
		}
	}
}
int LCA(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])return y;
	return x;
}
void add(int u,int v){
	E[++tot].v=v;
	E[tot].nxt=h[u];
	h[u]=tot;
}
int fid(int x){
	while(x!=f[x]){
		x=f[x]=f[f[x]];
	}
	return x;
}
bool cmp(node x,node y){
	return x.w<y.w;
}
void kul_tre(){
	for(int i=1;i<=n;i++)f[i]=i;
	int cnt=0,ans=0;
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++){
		int x=fid(e[i].u),y=fid(e[i].v);
		if(x==y)continue;
		cnt++;
		ans+=e[i].w;
		val[cnt]=e[i].w;
		f[cnt]=f[x]=f[y]=cnt;
		add(x,cnt);add(cnt,x);
		add(y,cnt);add(cnt,y);
		if(cnt==n-1)break;
	}
//	for(int i=1;i<=cnt;i++){
//		if(!vis[i]){
//			dfs1(i,0);
//			dfs2(i,i);
//		}
//	}
	dfs1(cnt,0);
	dfs2(cnt,cnt);
}
signed main() {
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		int w=read();
		e[i]={u,v,w};
	}
	kul_tre();
	int q=read();
	val[0]=-1;
	while(q--){
		int x=read(),y=read();
		cout<<val[LCA(x,y)];
	}
	return 0;
}