You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
75 lines
1.7 KiB
75 lines
1.7 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
const int N = 20010, M = 40010;
|
|
int n, m;
|
|
int f[N][16], depth[N];
|
|
int dist[N]; // 距离1号点的距离
|
|
|
|
// 邻接表
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
void add(int a, int b, int c) {
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
}
|
|
|
|
void bfs() {
|
|
// 1号点是源点
|
|
depth[1] = 1;
|
|
queue<int> q;
|
|
q.push(1);
|
|
while (q.size()) {
|
|
int u = q.front();
|
|
q.pop();
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
int v = e[i];
|
|
if (!depth[v]) {
|
|
q.push(v);
|
|
depth[v] = depth[u] + 1;
|
|
dist[v] = dist[u] + w[i];
|
|
f[v][0] = u; // 父亲大人
|
|
for (int k = 1; k <= 15; k++) // 记录倍增数组
|
|
f[v][k] = f[f[v][k - 1]][k - 1];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// 最近公共祖先
|
|
int lca(int a, int b) {
|
|
if (depth[a] < depth[b]) swap(a, b);
|
|
|
|
// 对齐
|
|
for (int k = 15; k >= 0; k--)
|
|
if (depth[f[a][k]] >= depth[b])
|
|
a = f[a][k];
|
|
|
|
if (a == b) return a;
|
|
|
|
// 齐步走
|
|
for (int k = 15; k >= 0; k--)
|
|
if (f[a][k] != f[b][k])
|
|
a = f[a][k], b = f[b][k];
|
|
// 返回父亲
|
|
return f[a][0];
|
|
}
|
|
|
|
int main() {
|
|
memset(h, -1, sizeof h);
|
|
scanf("%d %d", &n, &m);
|
|
int a, b, c;
|
|
// n-1条边
|
|
for (int i = 1; i < n; i++) {
|
|
scanf("%d %d %d", &a, &b, &c);
|
|
add(a, b, c), add(b, a, c);
|
|
}
|
|
|
|
bfs();
|
|
|
|
while (m--) {
|
|
scanf("%d %d", &a, &b);
|
|
int t = lca(a, b);
|
|
int ans = dist[a] + dist[b] - dist[t] * 2;
|
|
printf("%d\n", ans);
|
|
}
|
|
return 0;
|
|
} |