题目大意：求树上任意两点距离。
思路：
dis[i]表示i到根的距离（手动选根），则u、v的距离=dis[u]+dis[v]-2*dis[lca(u,v)]。
lca：u~v的dfs序列区间里，深度最小的节点即为u、v的lca（最近公共祖先），RMQ把它找到。
难点：
何为dfs序：
就是树上dfs依次遍历的节点编号的序列。它的特点是回溯时会【再次】经过非叶节点，非叶节点在dfs序中出现多次，且dfs序列个数>节点个数。
为什么要用dfs序：
因为u、v的lca只出现在u、v的dfs序间。比如树1 3、1 2。dfs遍历的节点依次为1 3 1 2。3、2的lca为其中间的1。
RMQ的dp[i][j]的理解：
请把dp[][]看成一维数组，也就是只看第一维来理解这句话：i：dfs序为i，j：以i开始，长度为2^j的区间里depth最小的dfs序节点。
初始状态：依次储存dfs序（即dp[i][0]=i）。
状态转移：看看两个子区间的两个值，哪个depth更小，该区间就可以更新了。
实现：
lca实现：dfs序储存+depth[]+RMQ
dfs序实现：pos[]（下标：节点编号，储存：dfs序）+ t[]（下标：dfs序，储存：节点编号）（最后的dis[]查询要节点编号）
（pos[]既可以存节点的第一个dfs序也可以存最后一个dfs序，因为dfs序区间保证了包含lca，而那个depth最小的就是lca，dp会把它找到）
dep[]实现：下标dfs序，储存对应编号的depth
RMQ实现：dp[i][j]
dis[]实现：dfs会遍历每个节点一次或多次，dis[v]=0表示第一次，更新，dis[v]！=0表示v是回溯，跳过。
static IO io=new IO();
static int n,m;
private static final int MAXN = 41000; static class Edge{
int v,next,dis; public Edge(int v, int next, int dis) {
this.v = v;
this.next = next;
this.dis = dis;
}
} // 边编号
static int size;
// 双向加边一定开2倍，数组越界异常在hdu里显示wa
static Edge[]edges=new Edge[MAXN<<1];
static int[]head=new int[MAXN];
static int[]dis=new int[MAXN]; // dfs序，dfs完成后的意义是dfs序长度
static int tot;
// 这三个数组下标都是dfs序，不刷新，因为tot从0开始会依次覆盖
static int[]pos=new int[MAXN<<1];
static int[]dep=new int[MAXN<<1];
static int[]t=new int[MAXN<<1]; // dp不刷新，因为状态转移只会处理子区间，2的次方保证可以对半分，手动赋初值
static int[][]dp=new int[MAXN<<1][22]; public static void main(String[] args) {
int T=io.nextInt();
while (T-->0){
n=io.nextInt();m=io.nextInt(); Arrays.fill(head,-1);
Arrays.fill(dis,0);
size=0;
for (int i = 0; i < n - 1; i++) {
int a=io.nextInt(),b=io.nextInt(),c=io.nextInt();
edges[size]=new Edge(b,head[a],c);
head[a]=size++;
edges[size]=new Edge(a,head[b],c);
head[b]=size++;
} tot=0;
dfs(1,0); for (int i=0;i<tot;i++)dp[i][0]=i;
for (int j=1;(1<<j)<=tot;j++){
for (int i=1;i+(1<<j)-1<=tot;i++){
dp[i][j]= dep[dp[i][j-1]]<dep[dp[i+(1<<j-1)][j-1]]?
dp[i][j-1]:dp[i+(1<<j-1)][j-1];
}
} while (m-->0){
int a=io.nextInt(),b=io.nextInt();
// 因为dp[u][k]的u一定要左节点,dp[v-(1<<k)+1][k]的v一定要右节点
int u=Math.min(pos[a],pos[b]),v= Math.max(pos[a],pos[b]); int k=(int)(Math.log(v-u+1)/Math.log(2));
int dfsfa=dep[dp[u][k]]<dep[dp[v-(1<<k)+1][k]]?
dp[u][k]:dp[v-(1<<k)+1][k];
int fa=t[dfsfa];
io.println(dis[a]+dis[b]-2*dis[fa]);
}
}
} static void dfs(int u,int de){
pos[u]=tot;dep[tot]=de;t[tot++]=u;
for (int i=head[u];i!=-1;i=edges[i].next){
if (dis[edges[i].v]!=0)continue;
dis[edges[i].v]=dis[u]+edges[i].dis;
dfs(edges[i].v,de+1);
// 这一步就保证了lca出现在u、v的dfs序间
// 如树1 3、1 2，dfs序为1 3 1 2，这一步保证了1 再次出现在3 2间
dep[tot]=de;t[tot++]=u;
}
}