题目大意

题目链接
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

1
2
3
4
5
6
7
8
9
10
11
2
3 2
1 2 10
3 1 15
1 2
2 3

2 2
1 2 100
1 2
2 1

Sample Output

1
2
3
4
10
25
100
100

分析

求树上两点最短距离， lca模板， 就是试试自己的板子。

离线tarjan

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
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef unsigned long long ull;
typedef pair<int, int> P;
#define ms(a, b) memset((a), (b), sizeof(a))
const int N = (int)1e5 + 5;
const int INF = 0x3f3f3f3f;

inline int read() {
    int res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9')  { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res + 1) : res;
}

struct edge {
    int u, v, w, ne;
}ed[N], eq[N]; // ed存边 eq离线存询问

int head[N], f[N], hq[N];
int dis[N], ans[N];
int vis[N];
int cnt, n, m, cnt1;

void init(){
    cnt = cnt1 = 0;
    for (int i = 0; i <= n; ++i){
        f[i] = i;
    }
    ms(head, -1);
    ms(hq, -1);
    ms(dis, 0);
    ms(vis, 0);
}
inline void add(int u, int v, int w){
    ed[cnt] = {u, v, w, head[u]};
    head[u] = cnt++;
}
inline void addq(int u, int v, int id){
	eq[cnt1] = {u, v, id, hq[u]}; // 在结构体里虽然还是w， 但是咱们用它表示id
	hq[u] = cnt1++;
}


inline int tofind(int x){
    return (f[x] == x) ? f[x] : (f[x] = tofind(f[x]));
}
inline void tojoin(int a, int b){
	a = tofind(a);
	b = tofind(b);
	if (a != b)
		f[b] = a;
}
void tarjan(int u){
	// 分为两部分， 第一部分 建树 第二部分 求ans
    // 第一部分， 建树
    vis[u] = 1;
    for (int i = head[u]; ~i; i = ed[i].ne){
        int &v = ed[i].v, &w = ed[i].w;
        if (vis[v]) continue;
        dis[v] = dis[u] + w; // v到根结点的距离
        tarjan(v);
        tojoin(u, v); // 这里直接连上(f[v] = u)就行, 
    }

    for (int i = hq[u]; ~i; i = eq[i].ne){ // 与u相关的边
    	int &v = eq[i].v, &id = eq[i].w;
    	if (vis[v] != 2) continue; // 2 是以为这离线过了的点
    	int lca = tofind(v);
    	ans[id] = dis[u] + dis[v] - 2 * dis[lca]; // 两点树上最小距离：即根到两点距离-两倍到其最近公共祖先距离
    }
    vis[u] = 2;
}

int t, u, v, w;
int main(){
	t = read();
    while(t--){
    	n = read(), m = read();
        init(); // init 要放在n之后， 因为这个又被卡了好长时间。。。。。。
        for (int i = 1; i < n; ++i){
        	u = read(), v = read(), w = read();
            add(u, v, w);
            add(v, u, w);
        }
        for (int i = 0; i < m; ++i){
        	u = read(), v = read();
            addq(u, v, i);
            addq(v, u, i);
        }
        tarjan(1);
        for (int i = 0; i < m; ++i){
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}

在线 倍增法

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
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

typedef unsigned long long ull;
typedef pair<int, int> P;
#define ms(a, b) memset((a), (b), sizeof(a))
const int N = (int)1e5 + 5;
const int INF = 0x3f3f3f3f;

inline int read() {
    int res = 0;bool f = 0;char ch = getchar();
    while (ch < '0' || ch > '9')  { if (ch == '-') f = 1; ch = getchar(); }
    while (ch <= '9' && ch >= '0') { res = (res << 3) + (res << 1) + ch - '0'; ch = getchar(); }
    return f ? (~ res + 1) : res;
}

struct edge{
	int u, v, w, ne;
}ed[N];

int head[N], dis[N], cnt, n, m;

int deep[N], fa[N][20];

inline void init(){
	ms(head, -1);
	cnt = 0;
	ms(deep, 0);
	ms(dis, 0);
}

inline void add(int u, int v, int w){
	ed[cnt] = {u, v, w, head[u]};
	head[u] = cnt++;
}

inline void dfs(int u, int pre){

	deep[u] = deep[pre] + 1; // deep数组表示深度
	fa[u][0] = pre;          // fa[i][j] 表示i的第2^j辈的祖先
	for (int i = 1; i < 20; ++i)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];  
		// fa[i][j] = fa[fa[i][j - 1]][j - 1]  i的第2^j辈的祖先 等于 i的第2^(j-1)辈的祖先的第2^(j-1)辈的祖先
	for (int i = head[u]; ~i; i = ed[i].ne){
		int v = ed[i].v;
		if(v == pre) continue;
		dis[v] = dis[u] + ed[i].w;
		dfs(v, u);
	}
}

inline int lca(int a, int b){
	if (deep[a] < deep[b]) swap(a, b);
	// 运用二进制的思想 使得deep[a] == deep[b] 比如 7 可以用4 2 1表示
	for (int i = 19; i >= 0; --i)
		if (deep[a] - (1 << i) >= deep[b])
			a = fa[a][i];
	
	if (a == b) return a;
	// 倍增 2^k 步的爬, 找最小的满足 a != b 的
	for (int i = 19; i >= 0; --i){
		if (fa[a][i] != fa[b][i])
			a = fa[a][i], b = fa[b][i];
	}
	return fa[a][0];
}
int t, u, v, w;
int main(){
	t = read();
	while(t--){
		n = read(), m = read();
		init();
		for (int i = 1; i < n; ++i){
			u = read(), v = read(), w = read();
			add(u, v, w);
			add(v, u, w);
		}
		dfs(1, 0);
		while(m--){
			u = read(), v = read();
			int x = lca(u, v);
			printf("%d\n", dis[u] + dis[v] - 2 * dis[x]);
		}
	}
	return 0;
}
1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan