记录一下
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 20010, M = N * 2;
int n, m;
int h[N], e[M], ne[M], w[M], idx; // 存储图
vector<PII> query[N]; // 存储询问
int dist[N]; // 当前的点到根节点的距离
int st[N]; // 当前遍历的点的编号
int res[N]; // 第i号查询的结果
int p[N]; // 并查集
// 并查集
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
// 建图
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
// 建立每个点到根节点的距离
void dfs(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
dist[j] = dist[u] + w[i];
dfs(j, u);
}
}
// tarjan算法
void tarjan(int u) {
st[u] = 1;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
// 如果当前的点还没有被遍历过
if (!st[j]) {
// 遍历当前的点
tarjan(j);
// 遍历好以及回溯了以后,将这个点添加到并查集中
p[j] = u;
}
}
// 遍历与当前的点有关的询问
for (auto item : query[u]) {
// 获取另一个点和询问的编号
int y = item.first, id = item.second;
// 如果这个点已经被遍历过了
if (st[y] == 2) {
// 获取两个点的公共祖宗结点
int anc = find(y);
// 获取距离
res[id] = dist[u] + dist[y] - dist[anc] * 2;
}
}
st[u] = 2;
}
int main () {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for (int i = 1; i <= m; i ++) {
int a, b;
scanf("%d%d", &a, &b);
if (a != b) {
query[a].push_back({b, i});
query[b].push_back({a, i});
}
}
for (int i = 1; i <= n; i ++) p[i] = i;
// 获取当前的点到根节点的距离
dfs(1, -1);
// tarjan算法
tarjan(1);
for (int i = 1; i <= m; i ++) {
printf("%d\n", res[i]);
}
}