http://acm.hdu.edu.cn/showproblem.php?pid=2586
dis[a]为根节点到a的距离那么2个节点的最短距离就是dis[a]-dis[b]-dis[lca(a,b)]*2
参考邹老板子，存一下。
倍增法：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=40005;
struct node
{int ch,dis;
};
vector<node> G[MX];
int rdis[MX];
int fa[22][MX],dep[MX];void dfs(int u,int f,int dis)
{fa[0][u]=f;rdis[u]=dis;dep[u]=dep[f]+1;for(int i=0;i<G[u].size();i++){int v=G[u][i].ch;if(v==f)continue;dfs(v,u,dis+G[u][i].dis);}
}
void init(int n)
{memset(fa,0,sizeof(fa));dep[0]=0;dfs(1,0,0);for(int k=0;k+1<20;k++){for(int v=1;v<=n+n;v++){if(!fa[k][v]){fa[k+1][v]=0;}else{fa[k+1][v]=fa[k][fa[k][v]];}}}
}
int lca(int u,int v)
{if(dep[u]>dep[v]){swap(u,v);}for(int k=0;k<20;k++){if((dep[v]-dep[u])>>k&1){v=fa[k][v];}}if(u==v)return u;for(int k=20-1;k>=0;k--){if(fa[k][u]!=fa[k][v]){u=fa[k][u];v=fa[k][v];}}return fa[0][u];}
int main()
{int t,n,m;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<=n;i++) G[i].clear();int i,j,k;for(int c=0;c<n-1;c++){scanf("%d%d%d",&i,&j,&k);G[i].push_back({j,k});G[j].push_back({i,k});}init(n);int a,b;while(m--){scanf("%d%d",&a,&b);int ans=rdis[a]+rdis[b]-rdis[lca(a,b)]*2;printf("%d\n",ans);}}return 0;
}