1 #include <iostream>  2 #include <cstring>  3 #include <cstdio>  4 #include <cstdlib>  5 #include <cmath>  6 #include <string>  7 #include <vector>  8 #include <list>  9 #include <map> 10 #include <queue> 11 #include <stack> 12 #include <bitset> 13 #include <algorithm> 14 #include <numeric> 15 #include <functional> 16 #include <set> 17 #include <fstream> 18  19 using namespace std; 20  21 const int maxn=40010; 22  23 struct edge{ 24     int from,to,cost,next; 25 }; 26 edge es[maxn*2]; 27 int head[maxn],idx; 28 int dis[maxn],N,M; 29 int U[maxn],V[maxn]; 30 int par[maxn],rankh[maxn]; 31 int LCA[maxn]; 32 bool used[maxn]; 33  34 void add_edge(int u,int v,int cost) 35 { 36     es[idx].from=u; 37     es[idx].to=v; 38     es[idx].cost=cost; 39     es[idx].next=head[u]; 40     head[u]=idx++; 41 } 42  43 void build_graph(int u,int v,int cost) 44 { 45     add_edge(u,v,cost); 46     add_edge(v,u,cost); 47 } 48  49 void init(int n) 50 { 51     for(int i=0;i<=n;i++) 52     { 53         par[i]=i; 54         rankh[i]=0; 55     } 56 } 57  58 int find(int x) 59 { 60     if(x==par[x]) return x; 61     else return par[x]=find(par[x]); 62 } 63  64 void tarjan(int u) 65 { 66     used[u]=true; 67     for(int  i=0;i<M;i++) 68     { 69         if(U[i]==u&&used[V[i]]) LCA[i]=find(V[i]); 70         if(V[i]==u&&used[U[i]]) LCA[i]=find(U[i]); 71     } 72     for(int i=head[u];i!=-1;i=es[i].next) 73     { 74         int v=es[i].to; 75         if(!used[v]){ 76             dis[v]=dis[u]+es[i].cost; 77             tarjan(v); 78             par[v]=u; 79         } 80     } 81 } 82  83 int main() 84 { 85 //    freopen("/Users/apple/Desktop/暑假/HDU 2586/HDU 2586/in","r",stdin); 86     int T; 87     scanf("%d",&T); 88     while(T--) 89     { 90         scanf("%d%d",&N,&M); 91         init(2*N); 92         memset(head,-1,sizeof(head)); 93         idx=0; 94         memset(used,false,sizeof(used)); 95         dis[1]=0; 96         for(int i=0;i<=N;i++) 97         { 98             U[i]=V[i]=LCA[i]=0; 99         }100         for(int i=0;i<N-1;i++)101         {102             int u,v,cost;103             scanf("%d%d%d",&u,&v,&cost);104             build_graph(u, v, cost);105         }106         for(int i=0;i<M;i++)107         {108             int u,v;109             scanf("%d%d",&u,&v);110             U[i]=u,V[i]=v;111         }112         tarjan(1);113         for(int i=0;i<M;i++)114         {115             int res=dis[U[i]]+dis[V[i]]-2*dis[LCA[i]];116             printf("%d\n",res);117         }118     }119     return 0;120 }