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.
InputFirst line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.OutputFor each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.Sample Input
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
Sample Output
10 25 100 100
给你一棵树，树上的边有权值，问你连点之间距离多少？LCA的模板题，试一下模板，顺带加深理解。
dis(a,b)=dis(a,根)+dis(b,根)-2*dis( lca(a,b) , 根)
#include <bits/stdc++.h> using namespace std; const int maxn=44000; int t,n,q; int dis[maxn],dep[maxn],que[maxn]; int p[maxn]; bool vis[maxn]; int fa[maxn][50]; struct node { int to,dis; node(int t,int d):to(t),dis(d){} }; vector <node> e[maxn]; void init () { for (int i=0;i<n;++i) e[i].clear(); memset(dis,0,sizeof dis); memset(dep,0,sizeof dep); memset(que,0,sizeof que); } void bfs (int x) { memset(vis,false,sizeof vis); int w=1,r=1; que[1]=x; dep[x]=0; dis[x]=0; p[x]=-1; vis[x]=true; while (w<=r){ int u=que[w];w++; for (int i=0;i<e[u].size();++i){ int v=e[u][i].to; if (vis[v]) continue; p[v]=u; vis[v]=true; dep[v]=dep[u]+1; dis[v]=dis[u]+e[u][i].dis; que[++r]=v; } } } void getfa () { for (int j=0;(1<<j)<=n;++j){ for (int i=1;i<=n;++i) fa[i][j]=-1; } for (int i=1;i<=n;++i){ fa[i][0]=p[i]; } for (int j=1;(1<<j)<=n;++j){ for (int i=1;i<=n;++i) if (fa[i][j]!=-1) fa[i][j]=fa[fa[i][j-1]][j-1]; } } int findlca (int x,int y) { if (dep[x]<dep[y]) swap(x,y); while (dep[x]>dep[y]){ int j=0; while (dep[fa[x][j]]>dep[y]) ++j; if (dep[fa[x][j]]==dep[y]){x=fa[x][j];break;}//这行很容易忘！！！！ x=fa[x][j-1]; } if (x==y) return y; while (x!=y){ int j=0; while (fa[x][j]!=fa[y][j]&&fa[x][j]!=-1) ++j; if (j==0) break; x=fa[x][j-1]; y=fa[y][j-1]; } return fa[x][0]; } int main() { //freopen("de.txt","r",stdin); scanf("%d",&t); //printf("t=%d ",t); while (t--){ init(); scanf("%d",&n); scanf("%d",&q); //printf("n= %d ",n); for (int i=0;i<n-1;++i){ int x,y,d; scanf("%d%d%d",&x,&y,&d); e[x].push_back(node(y,d)); e[y].push_back(node(x,d)); } bfs(1); getfa(); for (int i=0;i<q;++i){ int x,y; scanf("%d%d",&x,&y); //printf("%d %d ",x,y); int LCA=findlca(x,y); printf("%d ",dis[x]+dis[y]-2*dis[LCA]); } } return 0; }