1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #include<iostream>  5 #include<vector>  6 #include<cmath>  7 #include<map>  8 using namespace std;  9  10 const int mx=4e4+4; 11 struct N 12 { 13     int v,d; 14     N(int x,int y) 15     { 16         v=x; 17         d=y; 18     } 19 }; 20 vector<N>g[mx],q[mx]; 21 int father[mx]; 22 int dis[mx]; 23 bool vs[mx]; 24 int ans[mx]; 25  26 void Init(int n) 27 { 28     for (int i=1;i<=n;i++) 29     { 30         father[i]=i; 31         dis[i]=0; 32         vs[i]=false; 33         g[i].clear(); 34         q[i].clear(); 35     } 36 } 37  38 int Find(int x) 39 { 40     int w=x; 41     while (w!=father[w]) w=father[w]; 42     while (x!=father[x]) 43     { 44         int fa=father[x]; 45         father[x]=w; 46         x=fa; 47     } 48     return w; 49 } 50  51 void un(int x,int y) 52 { 53     int rx=Find(x); 54     int ry=Find(y); 55     father[y]=x; 56 } 57  58 void dfs(int u,int fa,int d) 59 { 60     dis[u]=d; 61     vs[u]=true; 62     for (int i=0;i<g[u].size();i++) 63     { 64         N k=g[u][i]; 65         if (vs[k.v]) continue; 66         dfs(k.v,u,d+k.d); 67     } 68     for (int i=0;i<q[u].size();i++) 69     { 70         N k=q[u][i]; 71         if (!vs[k.v]) continue; 72         ans[k.d]=dis[u]+dis[k.v]-2*dis[Find(k.v)]; 73     } 74     un(fa,u); 75 } 76  77 int main() 78 { 79     int n,m; 80     int t; 81     scanf("%d",&t); 82     while (t--) 83     { 84         scanf("%d%d",&n,&m); 85         Init(n); 86         for (int i=1;i<n;i++) 87         { 88             int u,v,w; 89             scanf("%d%d%d",&u,&v,&w); 90             g[u].push_back(N(v,w)); 91             g[v].push_back(N(u,w)); 92         } 93         for (int i=1;i<=m;i++) 94         { 95             int u,v; 96             scanf("%d%d",&u,&v); 97             q[u].push_back(N(v,i)); 98             q[v].push_back(N(u,i)); 99         }100         dfs(1,0,0);101         for (int i=1;i<=m;i++) printf("%d\n",ans[i]);102     }103 }