在dfs的过程中维护三个数组：
deep[i]，表示i点在树中的深度；
grand[x][i]，表示x的第2^i个祖先的节点编号；
dis[x][i]，表示x到它2^i祖
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int M=4e4+4;
const int maxlog=20;
struct node{
int id,val;
node(int id1=0,int val1=0):id(id1),val(val1){}
};
vector<node>e[M];
int deep[M],grand[M][maxlog],dis[M][maxlog],book[M],s,n,root;
void dfs(int x){
for(int i=1;i<=s;i++){
grand[x][i]=grand[grand[x][i-1]][i-1];//x的2^i祖先是它2^i-1祖先的2^i-1祖先
dis[x][i]=dis[x][i-1]+dis[grand[x][i-1]][i-1];//x到它2^i祖先的距离 = x到它2^i-1祖先的距离 + x的2^i-1祖先到它2^i-1祖先距离
if(!grand[x][i])//到子树跟了
break;
}
for(int i=0;i<e[x].size();i++){
int v=e[x][i].id;
if(v!=grand[x][0]){
grand[v][0]=x;维护父子关系
deep[v]=deep[x]+1;//维护深度
dis[v][0]=e[x][i].val;//维护距离
dfs(v);
}
}
}
void init(){
//n为节点个数
s=floor(log(n+0.0)/log(2.0));////最多能跳的2^i祖先
deep[0]=-1;////根结点的祖先不存在，用-1表示
dfs(root);以root为根节点建树
}
int LCA(int a,int b){
if(deep[a]>deep[b])//保证a在b上面，便于计算(floor:向下取整；ceil：向上取整）
swap(a,b);
int ans=0;
for(int i=s;i>=0;i--)//类似于二进制拆分，从大到小尝试
if(deep[a]<deep[b]&&deep[a]<=deep[grand[b][i]])//a在b下面且b向上跳后不会到a上面
ans+=dis[b][i],b=grand[b][i];//先把深度较大的b往上跳
for(int i=s;i>=0;i--)
if(grand[a][i]!=grand[b][i])//a,b的2^i祖先不一样 => 没跳到同样深度位置，接着跳
ans+=dis[a][i],a=grand[a][i],ans+=dis[b][i],b=grand[b][i];//一起往上跳
if(a!=b)//没跳到一个地方，那么再往上一个结点就是它们的LCA
ans+=dis[a][0],ans+=dis[b][0];
return ans;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int m;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
book[i]=0,e[i].clear(),deep[i]=0;
memset(grand,0,sizeof(grand));
memset(dis,0,sizeof(dis));
for(int i=1;i<n;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
book[y]=1;
e[x].push_back(node(y,w));
e[y].push_back(node(x,w));
}
for(int i=1;i<=n;i++){
if(!book[i]){
root=i;
break;
}
}
init();//cout<<"!!"<<endl;
while(m--){
int x,y;
scanf("%d%d",&x,&y);
printf("%d
",LCA(x,y));
}
}
return 0;
}
先的距离。