奇怪的知识又增加了呢！

  今天，我们来讲一下欧拉序的一个神奇的用处——求解LCA，这个神奇的方法求LCA有什么神奇的好处呢？它的预处理操作是的，但是查询操作是O(1)的。

  好了，直入主题，首先，怎样求解欧拉序呢？

  这幅图的欧拉序为：A - B - D - B - E - G - E - B - A - C - F - H - F - C - A

  很显然的，我们能发现，任意两点之间的路径一定存在于两点欧拉序之上，那么，很直白的，这条路径上的深度最浅的点不就是他们的LCA结点了嘛？连续区间段的最值问题求解，可以用数据结构来维护一下。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define eps 1e-8
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 4e4 + 7;
int N, Q, head[maxN], cnt;
struct Eddge
{
    int nex, to; ll val;
    Eddge(int a=-1, int b=0, ll c=0):nex(a), to(b), val(c) {}
}edge[maxN << 1];
inline void addEddge(int u, int v, ll w)
{
    edge[cnt] = Eddge(head[u], v, w);
    head[u] = cnt++;
}
inline void _add(int u, int v, ll w) { addEddge(u, v, w); addEddge(v, u, w); }
int deep[maxN], euler[maxN << 1], Esiz, rid[maxN], LOG_2[maxN << 1];
ll dis[maxN];
void dfs(int u, int fa)
{
    deep[u] = deep[fa] + 1; rid[u] = Esiz + 1;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == fa) continue;
        dis[v] = dis[u] + edge[i].val;
        euler[++Esiz] = u;
        dfs(v, u);
    }
    euler[++Esiz] = u;
}
int mn[maxN << 1][20] = {0};
inline void RMQ_Init()
{
    for(int i=1; i<=Esiz; i++) mn[i][0] = euler[i];
    for(int j=1; (1 << j) <= Esiz; j++)
    {
        for(int i=1; i + (1 << (j - 1)) + 1 <= Esiz; i++)
        {
            if(deep[mn[i][j - 1]] < deep[mn[i + (1 << (j - 1)) + 1][j - 1]]) mn[i][j] = mn[i][j - 1];
            else mn[i][j] = mn[i + (1 << (j - 1)) + 1][j - 1];
        }
    }
}
inline int Rmq(int l, int r)
{
    int det = r - l + 1, kk = LOG_2[det];
    if(deep[mn[l][kk]] <= deep[mn[r - (1 << kk) + 1][kk]]) return mn[l][kk];
    else return mn[r - (1 << kk) + 1][kk];
}
inline int _LCA(int u, int v)
{
    int l = rid[u], r = rid[v];
    if(l > r) swap(l, r);
    return Rmq(l, r);
}
inline void init()
{
    cnt = Esiz = 0;
    for(int i=1; i<=N; i++) { head[i] = -1; rid[i] = 0; }
}
int main()
{
    for(int i = 1, j = 2, k = 0; i < (maxN << 1); i++)
    {
        if(i == j) { j <<= 1; k ++; }
        LOG_2[i] = k;
    }
    int T; scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &N, &Q);
        init();
        for(int i=1, u, v, w; i<N; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            _add(u, v, w);
        }
        deep[0] = 0; dis[1] = 0;
        dfs(1, 0);
        deep[0] = INF;
        RMQ_Init();
        int u, v, lca;
        while(Q--)
        {
            scanf("%d%d", &u, &v);
            lca = _LCA(u, v);
            printf("%lld\n", dis[u] + dis[v] - 2LL * dis[lca]);
        }
    }
    return 0;
}