村里有 n n n 栋房子和一些双向的道路连接着他们。每天人们总喜欢这样问“如果我想从 A A A家到 B B B家有多远”？这个问题通常很难回答。但幸运的是，在这个村庄里，答案总是唯一的，因为道路的建造方式是每两栋房子之间都有一条唯一的简单路径（“唯一”意味着你不能用两种不同的方法去往同一个地方，“简单”意味着你不能经过同一条道路两次）。你的任务是回答这些好奇的人的所有问题
第一行是单个整数 T ( T ≤ 10 ) T(T\leq 10) T(T≤10)，表示测试用例的数量 对于每个测试用例，第一行有两个数字 n ( 2 ≤ n ≤ 40000 ) n(2\leq n\leq 40000) n(2≤n≤40000)和 m ( 1 ≤ m ≤ 200 ) m(1\leq m\leq 200) m(1≤m≤200)，即房屋数量和查询数。下面的 n − 1 n-1 n−1行由三个数字 i i i， j j j， k k k组成，用一个空格隔开，表示有一条道路连接 i i i号房子和 j j j号房子，长度 k ( 0 < k ≤ 40000 ) k(0<k\leq40000) k(0<k≤40000)，房屋的编号从 1 1 1到 n n n。
接下来的 m m m行中每行都有两个整数 i i i和 j j j，你需要回答房子 i i i和房子 j j j之间的距离。
对于每个测试用例，输出 m m m行。每次表示查询的答案
2 3 2 1 2 10 3 1 15 1 2 2 3
2 2 1 2 100 1 2 2 1
#include<bits/stdc++.h> using namespace std; int v[10005],pj[10005],ne[10005],h[10005],d[10005],di[10005],f[10005][10005],cnt=0,n,m,t,T; queue<int>q; void add(int x,int y,int z){ v[++cnt]=y; pj[cnt]=z; ne[cnt]=h[x]; h[x]=cnt; } void bfs_ycl(){ q.push(1); d[1]=1; while(q.size()){ int x=q.front();q.pop(); for(int i=h[x];i>=1;i=ne[i]){ int y=v[i]; if(d[y])continue; d[y]=d[x]+1; di[y]=di[x]+pj[i]; f[y][0]=x; for(int j=1;j<=t;j++){ f[y][j]=f[f[y][j-1]][j-1]; } q.push(y); } } } int lca(int x,int y){ if(d[x]>d[y])swap(x,y); for(int i=t;i>=0;i--){ if(d[f[y][i]]>=d[x]){ y=f[y][i]; } } if(x==y){ return x; } for(int i=t;i>=0;i--){ if(f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i]; } } return f[x][0]; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); t=(int)(log2(n))+1; memset(h,0,sizeof h); memset(d,0,sizeof d); cnt=0; for(int i=1,u,v,w;i<n;i++){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } bfs_ycl(); for(int i=1,u,v;i<=m;i++){ scanf("%d%d",&u,&v); printf("%d\n",di[u]+di[v]-2*di[lca(u,v)]); } } return 0; }