lca模板

https://www.luogu.com.cn/problem/P1967

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define x first 
#define y second

using namespace std;

const int N=6e4+10,mod=998244353;
const int LOGN=20;

typedef pair<int,int> PII;

struct Node{
	int a,b,c;	
}edges[N]; 

int p[N];
int par[N][22],val[N][22];
int dep[N];
vector<PII> e[N];
int n,m;

bool cmp(Node x,Node y){
	return x.c>y.c;
}

int find(int x){
	if(p[x]!=x) return p[x]=find(p[x]);
	return p[x];
}

void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	for(auto t:e[u]){
		int v=t.x,w=t.y;
		if(v==fa) continue;
		par[v][0]=u;
		val[v][0]=w;
		dfs(v,u);
	}
}

void slove(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edges[i]={u,v,w};
	}
	sort(edges+1,edges+1+m,cmp);
	
	for(int i=1;i<=m;i++){
		int a=edges[i].a,b=edges[i].b,c=edges[i].c;
		int pa=find(a),pb=find(b);
		if(pa==pb) continue;
		p[pa]=pb;
		e[a].push_back({b,c});
		e[b].push_back({a,c});
	}
	
	for(int i=1;i<=n;i++)
	if(p[i]==i) dfs(i,0);
	
	for(int j=1;j<=LOGN;j++)
	 for(int i=1;i<=n;i++){
	 	par[i][j]=par[par[i][j-1]][j-1];
	 	val[i][j]=min(val[i][j-1],val[par[i][j-1]][j-1]);
	 }
	
	int q;
	cin>>q;
	while(q--){
		int u,v;
		cin>>u>>v;
		if(find(u)!=find(v)){
			cout<<-1<<endl;
			continue;
		}
		if(dep[u]>dep[v]) swap(u,v);
		int d=dep[v]-dep[u];
		int ans=2e9+10;
		
		for(int i=LOGN;i>=0;i--)
		if(d>>i&1){
			ans=min(ans,val[v][i]);
			v=par[v][i];
		}
		if(u==v){
			cout<<ans<<endl;
			continue;
		}
		for(int i=LOGN;i>=0;i--) if(par[u][i]!=par[v][i]){
			ans=min(ans,min(val[u][i],val[v][i]));
			u=par[u][i];
			v=par[v][i];
		}
		ans=min(ans,min(val[u][0],val[v][0]));
		cout<<ans<<endl;
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T=1;
//	cin>>T;
	while(T--) slove(); 
}