这道题本质上就是要搞懂 无根树上任意两点距离就是 各自到根节点距离之和再减去两倍的lca节点到根节点距离
求lca我们这里可以采用Tarjan离线的方式~
#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=N*2;
typedef pair<int,int> PII;
int n,m,ne[M],h[N],e[M],idx,w[M],f[N],res[M],dist[N],st[N];
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void init(){
for(int i=1;i<=n;i++)f[i]=i;
}
int find(int x){
if(f[x]!=x)f[x]=find(f[x]);
return f[x];
}
vector<PII>q[N];
void dfs(int u,int fa){
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==fa)continue;
dist[j]=dist[u]+w[i];
dfs(j,u);
}
}
void tarjan(int u){
st[u]=1;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!st[j]){
tarjan(j);
f[j]=u;
}
}
for(auto item:q[u]){
int id=item.second,y=item.first;
if(st[y]==2){
int anc=find(y);
res[id]=dist[y]+dist[u]-2*dist[anc];
}
}
st[u]=2;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1, sizeof h);
for(int i=0;i<n-1;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
if(a!=b){
q[a].push_back({b,i});
q[b].push_back({a,i});
}
}
init();
dfs(1,-1);
tarjan(1);
for(int i=0;i<m;i++){
printf("%d\n",res[i]);
}
}