Kruskal 重构树模板题

#include<bits/stdc++.h>
using namespace std;
int const N=150000;
int val[N],pre[N],cnt,siz[N],son[N],top[N],fa[N],d[N];
int cha(int x)//并查集 
{
	if(pre[x]!=x) return pre[x]=cha(pre[x]);
	return pre[x];
}
void bing(int x,int y,int temp)
{
	int fx=cha(x),fy=cha(y);
	pre[fx]=temp;
	pre[fy]=temp;
}
struct Edge
{
	int to,next;
}q[N*2];
int head[N],vis[N];
void add(int u,int v)
{
	q[++cnt].next=head[u];
	q[cnt].to=v;
	head[u]=cnt;
}
struct node
{
	int u,v,w;
}p[N];
int dfs1(int x)//树链剖分 
{
	d[x]=d[fa[x]]+1;
	siz[x]=1;
	son[x]=-1;
	vis[x]=1;
	for(int i=head[x];i;i=q[i].next)
	{
		int v=q[i].to;
		if(d[v]!=0) continue;
		fa[v]=x;
		siz[x]+=dfs1(v);
		if(son[x]==-1||siz[v]>siz[son[x]]) son[x]=v;
	}
	return siz[x];
}
int sum=0;
void dfs2(int x,int t)
{
	top[x]=t;
	if(son[x]) dfs2(son[x],t);
	for(int i=head[x];i;i=q[i].next)
	{
		int v=q[i].to;
		if(v!=son[x]&&v!=fa[x]) dfs2(v,v);
	}
}
int lca(int x,int y)//树剖求LCA 
{
	while(top[x]!=top[y])
	{
		if(d[top[x]]>d[top[y]]) x=fa[top[x]];
		else y=fa[top[y]];
	}
	if(d[x]<d[y]) return x;
	return y;
}
int cmp(node x,node y)//最大（最小）生成树(这个视情况而定) 
{
	return x.w>y.w;
}
/*
此处若是最小生成树，则是大根堆，原图中两个点间所有路径上的边最大权值的最小值 =最小生成树上两点简单路径的边最大权值 
=Kruskal 重构树上两点 LCA 的点权。
此处若是最大生成树，则是小根堆，原图中两个点间所有路径上的边最小权值的最大值 =最大生成树上两点简单路径的边最小权值 
=Kruskal 重构树上两点 LCA 的点权。 
*/ 
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) pre[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>p[i].u>>p[i].v>>p[i].w;
	}
	sort(p+1,p+1+m,cmp);
	int sum=0;
	for(int i=1;i<=m;i++)//建树 
	{
		int fx=cha(p[i].u),fy=cha(p[i].v);
		if(fx!=fy)
		{
			sum++,++n;
			pre[fx]=pre[fy]=pre[n]=n;
			add(n,fx),add(n,fy);
			add(fx,n),add(fy,n);
			val[n]=p[i].w;
		}
		if(sum==n-1) break;
	}
	for(int i=1;i<=n;i++)//把整棵树扫完 
	{
		if(!vis[i])
		{
			int f=cha(i);
			dfs1(f),dfs2(f,f); 
		}
	}
	int q;
	cin>>q;
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(cha(a)!=cha(b)) cout<<-1<<endl;
		else cout<<val[lca(a,b)]<<endl;//面对询问，求树上两点最小边权就是两点lca的点权。 
	}
	return 0;
}