传送门

题目描述

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.

输入

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,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

样例

• Input
  2
  3 2
  1 2 10
  3 1 15
  1 2
  2 3

2 2

• Output
  10
  25
  100
  100

题解

• 题意：给一棵树，求两点的最短距离。
• 带权LCA。在原有的基础上用dis[i][j]表示节点i到i+(2^j)节点的距离，dis[i][0]就是i节点到父节点的距离，dis[i][j]=dis[i][j-1]+dis[father[i][j-1]][j-1]

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

#include
         
           #define INIT(a,b) memset(a,b,sizeof(a)) #define LL long long using namespace std; const int maxn=4e4+7; const int maxm=4e4+7; const int inf=1<<32-1; int Begin[maxn],fa[maxn][30],dis[maxn][30],lg[maxn],depth[maxn]; struct Edge{
         	int to,val,next; }ae[maxn<<1]; int tot=0,n,m; void Add(int x,int y,int w){
        	ae[tot]=(Edge){y,w,Begin[x]}; 	Begin[x]=tot++; } void Dfs(int now,int f){
        	depth[now]=depth[f]+1; 	fa[now][0]=f; 	for(int i=1;(1<
          
           <=depth[now];i++){
        		fa[now][i]=fa[fa[now][i-1]][i-1]; 		dis[now][i]=dis[now][i-1]+dis[fa[now][i-1]][i-1]; 	} 	for(int i=Begin[now];~i;i=ae[i].next){
        		if(ae[i].to!=f){
        			dis[ae[i].to][0]=ae[i].val; 			Dfs(ae[i].to,now); 		} 	} } int Lca(int x,int y){
        	int ans=0; 	if(depth[x]
           
            depth[y]){
        		int k=lg[depth[x]-depth[y]]-1; 		ans+=dis[x][k]; 		x=fa[x][k]; 	} 	if(x==y)return ans; 	for(int i=lg[depth[x]];i>=0;i--) 		if(fa[x][i]!=fa[y][i]){
        			ans+=dis[x][i];ans+=dis[y][i]; 			x=fa[x][i],y=fa[y][i]; 		} 	return ans+dis[x][0]+dis[y][0]; } int main(){
        	int t; 	for(int i=1;i