代码：
#include<stdio.h> #include<iostream> #include<algorithm> #include<math.h> #include<string.h> using namespace std; const int max_=8e4+1; int depth[max_];//节点深度 int gw[max_][25];//第 i 点到2^j父亲的距离 int fa[max_][25];//第 i 点的2^j父亲 bool vis[max_];//标记数组 int tot,N; struct Tree//树 { int to; int w; int next; }a[max_*2]; int edge[max_*2]; void add_edge(int x,int y,int w)//建树 { a[tot].to=y; a[tot].w=w; a[tot].next=edge[x]; edge[x]=tot++; } void dfs(int now,int deep)//dfs预处理 { if(vis[now]==0) { vis[now]=1; depth[now]=deep;//记录节点的深度 } for(int i=edge[now];i!=-1;i=a[i].next) { int to=a[i].to; if(vis[to]) continue; int w=a[i].w; gw[to][0]=w;//to到父亲的距离 fa[to][0]=now;//to的父亲节点 dfs(to,deep+1); } } void LCA_init(int n)//预处理 { for(int i=1;i<=n;i++) for(int j=1;j<=N;j++) { fa[i][j]=fa[fa[i][j-1]][j-1]; gw[i][j]=gw[fa[i][j-1]][j-1]+gw[i][j-1]; } } int LCA_Q(int u,int v) { int ans=0;//距离 if(depth[u]<depth[v]) swap(u,v);//保证大减小 int k; k=depth[u]-depth[v]; for(int i=0;(1<<i)<=k;i++) { if((1<<i)&k) ans+=gw[u][i],u=fa[u][i]; } if(u==v) return ans;//找到了就退出 for(int i=N;i>=0;i--) { if(fa[u][i]!=fa[v][i]) { ans+=gw[u][i], ans+=gw[v][i]; u=fa[u][i], v=fa[v][i]; } } return ans+=gw[v][0]+gw[u][0]; } void init(int n)//初始化 { memset(vis,0,sizeof(vis)); tot=0; N=(int)(log(n+0.0)/log(2)); memset(edge,-1,sizeof(edge)); } int main() { int t; cin>>t; while(t--) { int n,m; scanf("%d %d",&n,&m); init(n); for(int i=0;i<n-1;i++) { int u,v,w; scanf("%d %d %d",&u,&v,&w); add_edge(u,v,w); add_edge(v,u,w); } dfs(1,0); LCA_init(n); while(m--) { int u,v; scanf("%d %d",&u,&v); int L=LCA_Q(u,v); printf("%d ",L); } /* for(int i=1;i<=n;i++) printf("%d ",fa[i][2]);*/ } } /* 13 2 1 2 1 1 3 1 1 4 1 2 5 1 3 6 1 6 10 1 6 11 1 10 13 1 4 7 1 4 8 1 4 9 1 8 12 1 */ /* for(int x=max0;x>=0;x--) //注意！此处循环必须是从大到小!因为我们应该越提越“精确”， if(fa[u][x]!=fa[v][x]) //如果从小到大的话就有可能无法提到正确位置，自己可以多想一下 { u=fa[u][x]; v=fa[v][x]; } return fa[u][0]; //此时u、v的第一个父亲就是LCA。*/