记录编号	593826	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2013]货车运输	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	1.588 s
提交时间	2024-09-17 12:12:59	内存使用	4.64 MiB

#include<bits/stdc++.h>
using namespace std;
int f[200010],p[200010][25],w[200010][25],d[200010],n,ht,gt,q,cnt,he[200010],m;
struct node{
	int x;
	int y;
	int z;
}c[200010];
struct abc{
	int v;
	int nx;
	int z;
};
abc e[200010];
void add(int x,int y,int z){
	e[++cnt].v=y,e[cnt].nx=he[x],e[cnt].z=z,he[x]=cnt;
}
int find(int x){
	if(x==f[x])
	return x;
	return f[x]=find(f[x]);
}
void join(int x,int y){
	int rx=find(x),ry=find(y);
	f[ry]=rx;
}
void dfs(int x,int fa){
	d[x]=d[fa]+1;
	for(int i=he[x];i;i=e[i].nx){
		int v=e[i].v;
		if(v!=fa){
		w[v][0]=e[i].z;
		p[v][0]=x;
		dfs(v,x);	
		}
	}
}
int lca(int x,int y){
	int ans=INT_MAX;
	if(d[x]>d[y])
	swap(x,y);
	for(int i=20; i>=0; i--)
    if(d[p[y][i]]>=d[x]){
        ans=min(ans, w[y][i]);  
        y=p[y][i]; 
    }
	if(x==y)
	return ans;
	for(int i=20;i>=0;i--){
		if(p[y][i]==p[x][i])
		continue;
		else{
		    ans=min(ans,w[x][i]);
			x=p[x][i];
			ans=min(ans,w[y][i]);
			y=p[y][i];
		}
	}
	return min(ans,min(w[y][0],w[x][0]));
}
bool cmp1(node A,node B){
	return A.z>B.z;
}
int main(){
	freopen("truck.in","r",stdin);
	freopen("truck.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	f[i]=i;
	for(int i=1;i<=m;i++){
		cin>>c[i].x>>c[i].y>>c[i].z;
	}
	sort(c+1,c+m+1,cmp1);
	for(int i=1;i<=m;i++){
		int x=c[i].x,y=c[i].y,z=c[i].z;
		if(find(x)!=find(y)){
			add(x,y,z);
			add(y,x,z);
			join(x,y);
		}
	}
	for(int i=1;i<=n;i++){
		if(d[i]==0){
			dfs(i,0);
			p[i][0]=i;
			w[i][0]=INT_MAX;
		}
	}
	for(int i=1; i<=20; i++)
        for(int j=1; j<=n; j++){
            p[j][i]=p[p[j][i-1]][i-1]; 
            w[j][i]=min(w[j][i-1], w[p[j][i-1]][i-1]);
        }
    
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		int z=lca(x,y);
		if(find(x)!=find(y))
		cout<<-1<<endl;
		else
		cout<<z<<endl;
	}
	return 0;
}