倍增LCA

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5,M=log2(N)+5;
int n,q,f[N][M],d[N],dis[N];
vector<pair<int,int> >edge[N];
void dfs(int u){
	d[u]=d[f[u][0]]+1;
	for(int i=0;f[u][i];i++)
		f[u][i+1]=f[f[u][i]][i];
	for(auto to:edge[u]){
		int v=to.first,w=to.second;
		if(v!=f[u][0]){
			dis[v]=dis[u]+w;
			f[v][0]=u;
			dfs(v);
		}
	}
}
int LCA(int u,int v){
	if(d[u]<d[v]) swap(u,v);
	for(int i=19;i>=0;i--)
		if(d[f[u][i]]>=d[v]) u=f[u][i];
	if(u==v) return u;
	for(int i=19;i>=0;i--)
		if(f[u][i]!=f[v][i]){
			u=f[u][i];
			v=f[v][i];
		}
	return f[u][0];
}
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1,u,v,w;i<n;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		edge[u].push_back({v,w});
		edge[v].push_back({u,w});
	}
	dfs(1);
	while(q--){
		int u,v;
		scanf("%lld%lld",&u,&v);
		int l=LCA(u,v);
		printf("%lld\n",dis[u]+dis[v]-2*dis[l]);
	}
	return 0;
}