How far away HDU 2586 (LCA 樹上倍增 模闆)

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.

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

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<cmath>
#define LL long long 
#define mem(a, b) memset(a, b, sizeof(a))
#define N 50010
#define MOD
using namespace std;

int f[N][20], d[N], dist[N];
int ver[2*N], Next[N*2], edge[N*2], head[N];
int T, n, m, tot, t;
queue<int> q;

void add(int x, int y, int z) {//鄰接表 
	ver[++tot]=y, edge[tot]=z, Next[tot]=head[x], head[x]=tot;
}

void bfs() {
	q.push(1), d[1]=1;
	while(q.size()) {
		int x=q.front();
		q.pop();
		for(int i=head[x]; i; i=Next[i]) {
			int y=ver[i];
			if(d[y]) continue;
			d[y]=d[x]+1;//y是x的子節點，深度比x大1 
			dist[y]=dist[x]+edge[i]; //求出x,y之間的距離 
			f[y][0]=x;//記錄y的父節點是x 
			for(int j=1; j<=t; j++)
				f[y][j]=f[f[y][j-1]][j-1];//記錄從x向根節點走2^j步到達的節點 
			q.push(y);                      //如果不存在該節點了，就是它的父節點 
		}
	}
}

int lca(int x, int y) {
	if(d[x]>d[y]) swap(x, y);  //使得y的深度>=x的深度 
	for(int i=t; i>=0; i--) 
		if(d[f[y][i]]>=d[x]) y=f[y][i];//如果往上走後，y的深度還是比x大，則更新y 
	if(x==y) return x;//如果y==x，說明LCA==x 
	for(int i=t; i>=0; i--){ //在之前的更新後，x,y的深度一定是相同了的，這個時候同時向上更新x,y 
		if(f[x][i]!=f[y][i])//如果x,y的父節點不同，則更新 
			x=f[x][i], y=f[y][i];
		else 
			return f[x][0];//相同了，找到共同的父節點 
	} 
}

int main() {
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&n, &m);
		t=(int)(log(n)/log(2))+1;
		for(int i=1; i<=n; i++) head[i]=d[i]=0;
		tot=0;
		for(int i=1; i<n; i++) {
			int x, y, z;
			scanf("%d%d%d",&x, &y, &z);
			add(x, y, z), add(y, x, z);
		}
		bfs();
		for(int i=1; i<=m; i++) {
			int x, y;
			scanf("%d%d",&x, &y);
			printf("%d\n",dist[x]+dist[y]-2*dist[lca(x, y)]);
		}//x，y到根節點的距離減去兩倍的最近公共祖先到根節點的距離就是x,y之間最近的距離 
	}
}