题目大意

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