题目链接：

Time Limit: 2000/1000 MS (Java/Others)   

 Memory Limit: 32768/32768 K (Java/Others)

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

 

题意：

 

给一个无向图,问两点i和j之间的距离是多少;

 

思路：

 

由于询问规模大,所以就无向图转化成树,然后寻找lca,然后再算距离;

把lca转化成RMQ问题,我是用的线段树找的RMQ;

 

AC代码：

 

#include 
       
        using namespace std;const int N=4e4+4;typedef long long ll;const double PI=acos(-1.0);int n,m,t,dis[N],dep[N],vis[N],w[N];vector
        
         ve[N];queue
         
          qu;int u[N],v[N],d[N],fa[N],a[4*N],tot,first[N];struct Tree{    int l,r,ans;};Tree tree[8*N];void bfs()//bfs把图转化成树;{    qu.push(1);    vis[1]=1;    dep[1]=0;    while(!qu.empty())    {        int top=qu.front();        qu.pop();        int len=ve[top].size();        for(int i=0;i
          
           =dep[a[tree[2*node+1].ans]])tree[node].ans=tree[2*node+1].ans;    else tree[node].ans=tree[2*node].ans;}//tree[node].ans为数组里的lca的位置;void build(int node,int L,int R){    tree[node].l=L;    tree[node].r=R;    if(L>=R)    {        tree[node].ans=L;        return ;    }    int mid=(L+R)>>1;    build(2*node,L,mid);    build(2*node+1,mid+1,R);    Pushup(node);}int query(int node,int L,int R){    if(L<=tree[node].l&&R>=tree[node].r)return tree[node].ans;    int mid=(tree[node].l+tree[node].r)>>1;    if(R<=mid)return query(2*node,L,R);    else if(L>mid)return query(2*node+1,L,R);    else    {        int pos1=query(2*node,L,mid),pos2=query(2*node+1,mid+1,R);        if(dep[a[pos1]]>=dep[a[pos2]])return pos2;        else return pos1;    }}int main(){    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&m);        for(int i=1;i<=n;i++)        {            ve[i].clear();        }        for(int i=1;i