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 by 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 are to 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

 

题意：有一棵有n个节点的树，每条边上有一个权值代表这两个点之间的距离，现在m次询问：从节点a到节点b的路径长？

思路：预处理所有节点到根节点（定为节点1）的距离，以及所有节点的祖先信息（fa[i][j]表示节点 i 向上距离为 （1<<j）的祖先节点编号），计算a和b到根节点的距离和，减去两倍的最近公共祖先的到根节点的距离值。

代码如下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N = 4e4 + 5;int head[N], cnt;struct Edge{    int to, next;    int value;}e[2 * N];struct Node {    int fa[20];    int deep;    int sum;    bool state;}node[N];void insert(int u, int v, int value){    e[++cnt].to = v;    e[cnt].next = head[u];    e[cnt].value = value;    head[u] = cnt;    e[++cnt].to = u;    e[cnt].next = head[v];    e[cnt].value = value;    head[v] = cnt;}int cal(int x, int t){    for (int i = 0; i <= 19; i++)        if (t&(1 << i)) x = node[x].fa[i];    return x;}void dfs(int x){    node[x].state = 1;    for (int i = 1; i <= 19; i++)    {        if (node[x].deep<(1 << i))break;        node[x].fa[i] = node[node[x].fa[i - 1]].fa[i-1];///倍增处理祖先信息    }    for (int i = head[x]; i; i = e[i].next)    {        if (node[e[i].to].state) continue;        node[e[i].to].deep = node[x].deep+ 1;        node[e[i].to].fa[0] = x;        node[e[i].to].sum = node[x].sum+e[i].value;        dfs(e[i].to);    }}int lca(int x, int y)///求lca{    if (node[x].deep
          
           = 0; i--)        if (node[x].fa[i] != node[y].fa[i])        {            x = node[x].fa[i];            y = node[y].fa[i];        }    if (x == y)return x;    else return node[x].fa[0];}void init(){    cnt = 0;    memset(head, 0, sizeof(head));    memset(node, 0, sizeof(node));}int main(){    int T; cin >> T;    while (T--)    {        init();        int n, m; cin >> n >> m;        for (int i = 0; i < n-1; i++) {            int x, y, v; scanf("%d%d%d",&x,&y,&v);            insert(x,y,v);        }        dfs(1);        for (int i = 0; i < m; i++) {            int x, y; scanf("%d%d",&x,&y);            int pa = lca(x, y);            int ans = node[x].sum - node[pa].sum + node[y].sum - node[pa].sum;            cout << ans << endl;        }    }    return 0;}