用树链剖分求LCA的模板；
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 const int maxn=40005;
5 int n,m;
6 int head[maxn],to[maxn<<1],w[maxn<<1],nxt[maxn<<1],tot;
7 int fa[maxn],dep[maxn],son[maxn],top[maxn],size[maxn],dis[maxn];
8
9 void add(int x,int y,int z){
10 nxt[++tot]=head[x];
11 head[x]=tot;
12 to[tot]=y;
13 w[tot]=z;
14 }
15
16 void dfs1(int u,int f){
17 fa[u]=f,size[u]=1,dep[u]=dep[f]+1;
18 for(int i=head[u];i;i=nxt[i]){
19 int v=to[i];
20 if(v==f) continue;
21 dis[v]=dis[u]+w[i];
22 dfs1(v,u);
23 size[u]+=size[v];
24 if(size[v]>size[son[u]]) son[u]=v;
25 }
26 }
27
28 void dfs2(int u){
29 if(u==son[fa[u]]) top[u]=top[fa[u]];
30 else top[u]=u;//求top数组
31 for(int i=head[u];i;i=nxt[i]){
32 int v=to[i];
33 if(v!=fa[u]) dfs2(v);
34 }
35 }
36
37 int LCA(int u,int v){
38 while(top[u]!=top[v]){
39 if(dep[top[u]]>dep[top[v]]) u=fa[top[u]];
40 else v=fa[top[v]];
41 }
42 return dep[u]>dep[v]?v:u;
43 }
44
45 int main(){
46 int T;
47 scanf("%d",&T);
48 while(T--){
49 scanf("%d%d",&n,&m);
50 for(int i=1;i<=n;i++) head[i]=dep[i]=dis[i]=son[i]=0;
51 tot=0;
52 for(int i=1;i<n;i++){
53 int x,y,z;
54 scanf("%d%d%d",&x,&y,&z);
55 add(x,y,z);add(y,x,z);
56 }
57 dfs1(1,0);
58 dfs2(1);
59 for(int i=1;i<=m;i++){
60 int x,y;
61 scanf("%d%d",&x,&y);
62 int k=LCA(x,y);
63 printf("%d\n",dis[x]+dis[y]-2*dis[k]);
64 }
65 }
66 return 0;
67 }
