题目大意：
城镇之间互相有道路（双向边），且只存在n-1条边，保证相互可达，求两点
之间的距离。
思路：
转化为LCA裸问题，只需要再一边寻找最近公共祖先的同时，跟
新当前点到根节点的距离dist即可，那么节点u,v之间的距离为
dist[u]+dist[v]-2*dist[lca(u,v)];
代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int maxn=40005;
const int maxm=80005;
struct enode {
int to,next,w;
} edges[maxm];
struct qnode {
int to,next,id;
} query[405];
//dist[] 节点到根节点的距离
int head_e[maxn],head_q[maxn],f[maxn],vis[maxn],dist[maxn],res[405];
int n,m,u,v,w,cnte=0,cntq=0;//n个节点 m个询问
inline void addedge(int u, int v, int w) {
edges[cnte].w=w;
edges[cnte].to=v;
edges[cnte].next=head_e[u];
head_e[u]=cnte++;
}
inline void addque(int u, int v, int id) {
query[cntq].id=id;
query[cntq].to=v;
query[cntq].next=head_q[u];
head_q[u]=cntq++;
}
inline void init() {
memset(head_e,-1,sizeof(head_e));
memset(head_q,-1,sizeof(head_q));
memset(vis,0,sizeof(vis));
memset(dist,0,sizeof(dist));
for(int i=1; i<=n; ++i) f[i]=i;
}
int Find(int x) {
return x==f[x] ? x : f[x]=Find(f[x]);
}
void tarjan(int s) {
vis[s]=1;
for(int i=head_e[s]; i!=-1; i=edges[i].next) {
if(!vis[edges[i].to]) {
dist[edges[i].to]=dist[s]+edges[i].w;//跟新到根的距离
tarjan(edges[i].to);
f[edges[i].to]=s;
}
}
for(int i=head_q[s]; i!=-1; i=query[i].next) {
if(vis[query[i].to]==1) {
int z=Find(query[i].to);
//先减去再相加
res[query[i].id]=dist[s]-dist[z]-dist[z]+dist[query[i].to];
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t; cin>>t;
while(t--) {
cin>>n>>m;
init();
for(int i=1; i<n; ++i) {
cin>>u>>v>>w;
addedge(u,v,w);
addedge(v,u,w);
}
for(int i=1; i<=m; ++i) {
cin>>u>>v;
addque(u,v,i);
addque(v,u,i);
}
dist[1]=0;
tarjan(1);
for(int i=1; i<=m; ++i) cout<<res[i]<<endl;
}
return 0;
}