XJOI7141时空隧道求助

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
int n,m,l,mass,minn,cnt=0,ks,js;
int Log[100005],fa[100005],d[100005],dep[100005],f[100005][20];
struct pos{
	int x,y,w;
}edge[260820];
struct node{
	int to,val;
}bian[260820];
vector<node>t[100005];
bool cmp(pos a,pos b){
	return a.w>b.w;
}
void init(){
    scanf("%d%d%d",&n,&m,&mass);
    for(int i=1;i<=n;i++) fa[i]=i;
    Log[1]=0;Log[2]=1;
    for(int i=3;i<=n;i++) Log[i]=Log[i/2]+1;
    for(int i=1;i<=m;i++)
    	scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
	sort(edge+1,edge+m+1,cmp);
	scanf("%d",&l);
	
}
int find(int g){
	if(fa[g]!=g)
		fa[g]=find(fa[g]);
	return fa[g];
}
void add(int p,int q,int r){
	node tmp;
	tmp.to=q;
	tmp.val=r;
	t[p].push_back(tmp);
	return;
}
void dfs(int u,int fa){
	f[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int i=0;(1<<i)<=dep[fa];i++)
		f[u][i+1]=f[f[u][i]][i];
	for(int i=0;i<t[u].size();i++){
		int v=t[u][i].to;
		if(v!=fa){
			d[v]=t[u][i].val;
			dfs(v,u);
		}
	}
	return;
}
void kruskal(){
	for(int i=1;i<=m;i++){
		int u=find(edge[i].x);
		int v=find(edge[i].y);
		if(u==v) continue;
		else{
			cnt++;
			fa[u]=v; 
			add(u,v,edge[i].w);
			add(v,u,edge[i].w);
		}
		if(cnt==n-1) return;
	}
}
int lca(int u,int v){
	minn=inf;
	if(dep[u]<dep[v]) swap(u,v);
	while(dep[u]>dep[v]){
		minn=min(minn,d[u]);
		u=f[u][Log[dep[u]-dep[v]]];
	}
	if(u==v) return u;
	for(int i=Log[dep[u]];i>=0;i--){
		if(f[u][i]!=f[v][i]){
			minn=min(minn,d[u]);
			minn=min(minn,d[v]);
			u=f[u][i];
			v=f[v][i];
		}
	}
	minn=min(minn,d[u]);
	minn=min(minn,d[v]);
	return f[u][0];
}
int main(){
    init();
	kruskal();
	dfs(1,0);
	while(l--){
		scanf("%d%d",&ks,&js);
		int kkk=lca(ks,js);
		printf("%d\n",minn/mass);
	}
    return 0;
}
/*
zdsrs
2019/7/17
XJOI7141 时空隧道
*/