Problem Description
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.
Input
First 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.
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.
Output
For 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
Source
题目大意：
共有t组数据
给你n个点，n-1条双向边
有m次询问 问x~y点之间的距离是多少
1 #include <cstring> 2 #include <ctype.h> 3 #include <cstdio> 4 5 const int MAXN=40010; 6 7 int t,n,m; 8 9 struct node { 10 int to; 11 int next; 12 int val; 13 }; 14 node e[MAXN<<1]; 15 16 int head[MAXN],tot; 17 18 int deep[MAXN],f[MAXN][21],dis[MAXN]; 19 20 inline void read(int&x) { 21 int f=1;register char c=getchar(); 22 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 23 for(;isdigit(c);x=x*10+c-48,c=getchar()); 24 x=x*f; 25 } 26 27 inline void add(int x,int y,int v) { 28 e[++tot].to=y; 29 e[tot].val=v; 30 e[tot].next=head[x]; 31 head[x]=tot; 32 } 33 34 void dfs(int u) { 35 deep[u]=deep[f[u][0]]+1; 36 for(int i=head[u];i!=-1;i=e[i].next) { 37 int to=e[i].to; 38 if(!deep[to]&&to) { 39 f[to][0]=u; 40 dis[to]=dis[u]+e[i].val; 41 dfs(to); 42 } 43 } 44 return; 45 } 46 47 inline void swap(int&x,int&y) { 48 int t=x; 49 x=y;y=t; 50 return; 51 } 52 53 inline int LCA(int x,int y) { 54 if(deep[x]<deep[y]) swap(x,y); 55 int t=deep[x]-deep[y]; 56 for(int i=20;i>=0;--i) 57 if(deep[f[x][i]]>=deep[y]) x=f[x][i]; 58 if(x==y) return x; 59 for(int i=20;i;--i) 60 if(f[x][i]!=f[y][i]) 61 x=f[x][i],y=f[y][i]; 62 return f[x][0]; 63 64 } 65 66 inline void pre() { 67 tot=1; 68 memset(head,-1,sizeof head); 69 memset(deep,0,sizeof deep); 70 memset(dis,0,sizeof dis); 71 } 72 73 int hh() { 74 int x,y,z; 75 read(t); 76 while(t--) { 77 read(n);read(m); 78 pre(); 79 for(int i=1;i<n;++i) { 80 read(x);read(y);read(z); 81 add(x,y,z); 82 add(y,x,z); 83 } 84 dfs(1); 85 for(int j=1;j<=20;++j) 86 for(int i=1;i<=n;++i) 87 f[i][j]=f[f[i][j-1]][j-1]; 88 for(int i=1;i<=m;++i) { 89 read(x);read(y); 90 int lca=LCA(x,y); 91 printf("%d ",dis[x]+dis[y]-2*dis[lca]); 92 } 93 } 94 return 0; 95 } 96 97 int sb=hh(); 98 int main() {;}