There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.InputFirst line is a single integer T(T<=10), indicating the number of test cases.

  For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.

  Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.OutputFor each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.Sample Input

23 21 2 103 1 151 22 32 21 2 1001 22 1

Sample Output

1025100100 LCA倍增

1 #include
     
       2 #include
      
        3 #include
       
         4  5 using namespace std; 6  7 const int maxn=40005; 8 const int LOG = 20; 9 int par[maxn][LOG],dep[maxn];10 int head[maxn],dis[maxn];11 int cnt=0;12 13 struct EDGE14 {15     int v,w,next;16 }edge[maxn*2];17 18 void addedge(int u,int v,int w)19 {20     edge[cnt].v=v;21     edge[cnt].w=w;22     edge[cnt].next=head[u];23     head[u]=cnt++;24 }25 26 void dfs(int u,int fa,int depth){27     dep[u]=depth;28     if(u==1)29     { 30        for(int i=0;i
        
         =0;i--)59     {  60         if(par[u][i]!=par[v][i])61         {62             u=par[u][i];63             v=par[v][i];64         }65     }66     return par[u][0];67 }68 69 int main()70 {71     int T,n,m;72     cin>>T;73     while(T--)74     {75         cin>>n>>m;76         cnt=0;77         memset(head,-1,sizeof(head));78         int x,y,z;79         for(int i=0;i