在一棵树上 求2个点的最短距离。那么首先利用LCA找到2个点的近期公共祖先

公式：ans = dis(x) + dis(y) - 2 * dis(lca(x,y))

这里的dis(x)指的上x距离根节点的距离

注意一些细节方面，比方数组的越界问题：

#include<cstdio>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

const int maxn = 45555;

struct Edge{

    int to;

    LL  dist;

    Edge(int to,LL dist):to(to),dist(dist){};

};

int n,m;

int deep[maxn],pa[maxn][22];

LL  dis[maxn];

vector<Edge>G[maxn];

void init(){

    memset(pa,-1,sizeof(pa));

    for(int i = 1; i <= n; i++) G[i].clear();

}

//----------------LAC---------------------------

void dfs(int pos,int d,LL dist){

    //printf("[%d %d]\n",pos,dist);

    deep[pos] = d;

    dis[pos] = dist;

    int Size = G[pos].size();

    for(int i = 0; i < Size; i++)

        dfs(G[pos][i].to,d + 1,dist + G[pos][i].dist);

}

void lca_init(){

    for(int j = 1; (1 << j) <= n; j++)

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

            if(pa[i][j - 1] != -1)

                pa[i][j] = pa[pa[i][j - 1]][j - 1];

}

int lca(int a,int b){

    if(a == b)

        return a;

    if(deep[a] < deep[b])   swap(a,b);

    int i;

    for(i = 0;(1 << i) <= deep[a]; i++);

    for(int j = i; j >= 0; j--)

        if(pa[a][j] != -1 && deep[pa[a][j]] >= deep[b])

            a = pa[a][j];

    if(a == b)

        return b;

    for(int j = i; j >= 0; j--)

        if(pa[a][j] != -1 && deep[pa[a][j]] != deep[pa[b][j]]){

            a = pa[a][j];

            b = pa[b][j];

        }

    return pa[a][0];

}

//-------------------------------------------------

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

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

        int x,y,z;

        init();

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

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

            G[x].push_back(Edge(y,z));

            pa[y][0] = x;

        }

        for(int i = 1; i <= n; i++)if(pa[i][0] == -1){

            dfs(i,0,0);

            break;

        }

        lca_init();

        for(int i = 0; i < m; i++){

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

            LL ans = dis[x] + dis[y] - 2 * dis[lca(x,y)];

            printf("%I64d\n",ans);

        }

    }

    return 0;

}