P1967 st+树剖 15pts求助

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e5+5;
int n,m,q;
bool use[M];
struct node{int u,v,w;}e[M];
bool cmp(node n1,node n2){return n1.w>n2.w;}
vector<int>edge[N]; 
int fat[N];
int find(int x){return x==fat[x]?x:fat[x]=find(fat[x]);}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x!=y)
		fat[x]=y;
}
int dp[N][21],a[N],lg[N];
void build()
{
	lg[0]=-1;
	for(int i=1;i<=n;++i)
		dp[i][0]=a[i],lg[i]=lg[i>>1]+1;
	for(int j=1;j<=20;++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
			dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
	int k=lg[r-l+1];
	return min(dp[l][k],dp[r-(1<<k)+1][k]);
} 
int fa[N],son[N],sz[N],dep[N];
int dfn[N],top[N],id;
void dfs1(int u,int f)
{
	fa[u]=f;
	son[u]=-1;
	sz[u]=1;
	dep[u]=dep[f]+1;
	for(auto &v:edge[u])
	{
		if(v==f)
			continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(son[u]==-1||sz[v]>sz[son[u]])
			son[u]=v;
	}
}
void dfs2(int u,int t)
{
	dfn[u]=++id;
	top[u]=t;
	if(~son[u])
		dfs2(son[u],t);
	for(auto &v:edge[u])
		if(v!=son[u]&&v!=fa[u])
			dfs2(v,v);
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		fat[i]=i;
	for(int i=1;i<=m;++i)
		cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;++i)
	{
		if(find(e[i].u)!=find(e[i].v))
		{
			merge(e[i].u,e[i].v);
			edge[e[i].u].emplace_back(e[i].v);
			edge[e[i].v].emplace_back(e[i].u);
			use[i]=1;
		}
	}
	dfs1(1,0);
	dfs2(1,1);
	memset(a,0x3f,sizeof a);
	for(int i=1;i<=m;++i)
		if(use[i])
		{
			int u=e[i].u,v=e[i].v,w=e[i].w;
			if(dep[u]<dep[v])
				a[dfn[v]]=w;
			else
				a[dfn[u]]=w;
		}
	build();
	cin>>q;
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		if(find(x)!=find(y))
		{
			cout<<"-1\n";
			continue;
		}
		int ans=0x3f3f3f3f;
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])
				swap(x,y);	
			ans=min(ans,query(dfn[top[x]],dfn[x]));
			x=fa[top[x]];
		}
		if(dep[x]>dep[y])
			swap(x,y);
		cout<<min(ans,query(dfn[x],dfn[y]))<<'\n'; 
	}
}