1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #include<cstdio>  5 #include<sstream>  6 #include<vector>  7 #include<stack>  8 #include<queue>  9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,ll> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn=40000+5; 17  18 int n, m; 19 int num; 20 int tot; 21 int head[maxn]; 22 int vis[maxn]; 23 int ver[2*maxn]; 24 int deep[2*maxn]; 25 int dir[maxn]; 26 int first[maxn]; 27 int dp[2*maxn][25]; 28  29 struct node 30 { 31     int v,w; 32     int next; 33 }e[2*maxn]; 34  35 void addEdge(int u, int v, int w) 36 { 37     e[num].v=v; 38     e[num].w=w; 39     e[num].next=head[u]; 40     head[u]=num++; 41 } 42  43 void dfs(int u, int dep) 44 { 45     vis[u]=1; 46     ver[++tot]=u;   //遍历序列 47     first[u]=tot;   //结点第一次出现位置 48     deep[tot]=dep;     //深度 49     for(int i=head[u];i!=-1;i=e[i].next) 50     { 51         if(!vis[e[i].v]) 52         { 53             int v=e[i].v, w=e[i].w; 54             dir[v]=dir[u]+w;   //距离 55             dfs(v,dep+1); 56             ver[++tot]=u;      //回溯 57             deep[tot]=dep; 58         } 59     } 60 } 61  62 void ST(int n) 63 { 64     for(int i=1;i<=n;i++)  dp[i][0]=i; 65     for(int j=1;(1<<j)<=n;j++) 66         for(int i=1;i+(1<<j)-1<=n;i++) 67         { 68             int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1]; 69             dp[i][j]=deep[a]<deep[b]?a:b; 70         } 71 } 72  73 int RMQ(int L, int R) 74 { 75     int k=0; 76     while((1<<(k+1))<=R-L+1)  k++; 77     int a=dp[L][k], b=dp[R-(1<<k)+1][k]; 78     return deep[a]<deep[b]?a:b; 79 } 80  81 int LCA(int u, int v) 82 { 83     int x=first[u], y=first[v];   //查找出他最先出现的地方 84     if(x>y)  swap(x,y); 85     int res=RMQ(x,y);    //查询出的是他祖先的下标 86     return ver[res]; 87 } 88  89 int main() 90 { 91     //freopen("in.txt","r",stdin); 92     int T; 93     scanf("%d",&T); 94     while(T--) 95     { 96         num=0; tot=0; 97         memset(head,-1,sizeof(head)); 98         memset(vis,0,sizeof(vis)); 99         scanf("%d%d",&n,&m);100         for(int i=1;i<n;i++)101         {102             int u,v,w;103             scanf("%d%d%d",&u,&v,&w);104             addEdge(u,v,w);105             addEdge(v,u,w);106         }107         dir[1]=0;108         dfs(1,1);109         ST(2*n-1);110         while(m--)111         {112             int u,v;113             scanf("%d%d",&u,&v);114             int lca=LCA(u,v);115             printf("%d\n",dir[u]+dir[v]-2*dir[lca]);116         }117     }118     return 0;119 }