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.

2

3 2

1 2 10

3 1 15

1 2

2 3

2 2

1 2 100

1 2

2 1

10

25

100

100
典型的带权LCA

#include<bits/stdc++.h>

using namespace std;

const int N=1E5+;

typedef long long ll;

struct stu{

    int a,b;

};

vector<stu>ve[N];

ll bits[];

int step[N];

int depth[N];

int fa[N][];

void inint(){

    bits[]=;

    for(int i=;i<;i++) bits[i]=bits[i-]<<;

}

void dfs(int x,int y){

    depth[x]=depth[y]+;

    for(int i=;i<ve[x].size();i++){

        if(ve[x][i].a==y){

            step[x]=step[y]+ve[x][i].b;

        }

    }

    fa[x][]=y;

    for(int i=;i<;i++) fa[x][i]=fa[fa[x][i-]][i-];

    for(int i=;i<ve[x].size();i++){

        int dx=ve[x][i].a;

        if(dx!=y){

            dfs(dx,x);

        }

    }

}

int lca(int x,int y){

    if(depth[x]<depth[y]) swap(x,y);

    int dif=depth[x]-depth[y];

    for(int i=;i>=;i--){

        if(dif>=bits[i]){

            x=fa[x][i];

            dif=dif-bits[i];

        }

    }

    if(x==y) return x;

    for(int i=;i>=;i--){

        if(depth[x]>=bits[i]&&fa[x][i]!=fa[y][i]){

            x=fa[x][i];

            y=fa[y][i];

        }

    }

    return fa[x][];

}

int main(){

    int t;

    inint();

    scanf("%d",&t);

    while(t--){

        int n,m;

        scanf("%d%d",&n,&m);

        int x,y,z;

        for(int i=;i<=n;i++){

            ve[i].clear();

        }

        memset(depth,,sizeof(depth));

        memset(fa,,sizeof(fa));

        memset(step,,sizeof(step));

        for(int i=;i<=n-;i++){

            scanf("%d%d%d",&x,&y,&z);

            ve[x].push_back({y,z});

            ve[y].push_back({x,z});

        }

        dfs(,);

        while(m--){

            int x1,y1;

            scanf("%d%d",&x1,&y1);

            int point=lca(x1,y1);

            printf("%d\n",step[x1]+step[y1]-*step[point]);

        }

    }

    return ;

}