Problem Description

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.

 

 

Input

First 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.

 

 

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

 

 

Sample Input

2

3 

2

1 2 10

3 1 15

1 2

2 3

 

2 2

1 2 

100

1 2

2 1

 

 

Sample Output

10

25

100

100

 

 

 

 

题意：给出一棵树，m个询问

每次询问给出a,b

问a,b的距离。

 

siz[i]  表示i到根节点的距离

 

思路：先求出lca=LCA(a,b)

 

则距离 = siz[a]+siz[b]-2*siz[lca]

 

 

 

1 #include
        
           2 #include
         
            3 #include
          
             4   5 using namespace std;  6   7 const int maxn=40000+5;  8   9 struct Edge 10 { 11     int to,next,w; 12 }edge[maxn<<1]; 13 int head[maxn]; 14 int tot; 15 int p[maxn][24]; 16 int siz[maxn]; 17 int dep[maxn]; 18  19 void init(int n) 20 { 21     tot=1; 22     memset(head,-1,sizeof(head)); 23     memset(siz,0,sizeof(siz)); 24     memset(dep,0,sizeof(dep)); 25  26     for(int i=1;i<=n;i++) 27         for(int j=0;j<24;j++) 28             p[i][j]=-1; 29 } 30  31 void addedge(int u,int v,int w) 32 { 33     edge[tot].to=v; 34     edge[tot].w=w; 35     edge[tot].next=head[u]; 36     head[u]=tot++; 37 } 38  39 void dfs(int n,int u,int fa) 40 { 41     for(int i=head[u];~i;i=edge[i].next) 42     { 43         int v=edge[i].to; 44         int w=edge[i].w; 45         if(!dep[v]&&v!=fa) 46         { 47             dep[v]=dep[u]+1; 48             p[v][0]=u; 49             siz[v]=siz[u]+w; 50             dfs(n,v,u); 51         } 52     } 53 } 54  55 void init_lca(int n) 56 { 57     for(int j=1;(1<
           
            <=n;j++) 58     { 59         for(int i=1;i<=n;i++) 60         { 61             if(p[i][j-1]!=-1) 62             { 63                 p[i][j]=p[p[i][j-1]][j-1]; 64             } 65         } 66     } 67 } 68  69 int solve(int n,int u,int v) 70 { 71     if(u==v) 72         return 0; 73     if(dep[u]
            
             =0;j--) 87     { 88         if(dep[u]-(1<
             
              =dep[v]) 89 u=p[u][j]; 90 } 91 92 if(u==v) 93 return (siz[init_u]-siz[u]); 94 95 for(int j=cnt;j>=0;j--) 96 { 97 if(p[u][j]!=-1&&p[u][j]!=p[v][j]) 98 { 99 u=p[u][j];100 v=p[v][j];101 }102 }103 int lca=p[u][0];104 105 return (siz[init_u]+siz[init_v]-2*siz[lca]);106 107 }108 109 int main()110 {111 int test;112 scanf("%d",&test);113 114 while(test--)115 {116 int n,m;117 scanf("%d%d",&n,&m);118 119 init(n);120 121 for(int i=1;i