<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
倍增
需求是处理m次查询,每次查询的结果是给定树结构中任意两节点之间的最短距离,虽然是多源最短路,但显然1万的最大节点数,跑$O(n^3)$的Floyd算法会TLE,由于给定的是树结构,因此随意指定一个节点为根之后,再查询任意两节点之间的最短距离,就可以用求最近公共祖先(LCA)的方法了
假设查询的节点为$(s,e)$,它们的最近公共祖先为$a$,那么从$s$出发必然先经过$a$再到达$e$
用dist[i]表示根节点到i节点的距离,那么前半程的距离为$dist[s]-dist[a]$,后半程的距离为$dist[e]-dist[a]$,相加得结果为$dist[s]+dist[e]-2*dist[a]$,$a$就是我们需要求的$lca(s,e)$
lca函数的细节在1172.祖孙询问中已经介绍过,可以去那儿看
本问题除了多了一条dist表以外,和1172完全一致
时间复杂度
$O((n+m)*log(n))$
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <queue>
#include <vector>
using namespace std;
using Node = pair<int, int>;
//O2优化下,邻接表法和链式前向星法的微小性能差距可以忽略
vector<vector<Node>> adjList;
vector<int> depth, dist;
vector<vector<int>> pre;
queue<int> q;
int n, m, s, e, v;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
depth.resize(n + 1, 1e9 + 7);
dist.resize(n + 1, 1e9 + 7);
adjList.resize(n + 1);
pre.resize(n + 1, vector<int>(15, 0));
for (int i = 1; i < n; i++) {
cin >> s >> e >> v;
adjList[s].push_back({ e, v });
adjList[e].push_back({ s, v });
}
int root = 1;
//这里构造两条线性表depth和dist,分别存放深度和距离
depth[0] = dist[0] = dist[root] = 0;
depth[root] = 1;
q.push(root);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto& [nx, val] : adjList[cur]) {
if (depth[nx] > depth[cur] + 1) {
depth[nx] = depth[cur] + 1;
dist[nx] = dist[cur] + val;
q.push(nx);
pre[nx][0] = cur;
for (int i = 1; i <= 14; i++) pre[nx][i] = pre[pre[nx][i - 1]][i - 1];
}
}
}
//lca函数依据的是深度而不是距离,跟1172完全一致
function<int(int, int)> lca = [=](int s, int e)-> int {
if (depth[s] < depth[e]) swap(s, e);
for (int i = 14; i >= 0; i--) {
if (depth[pre[s][i]] >= depth[e]) s = pre[s][i];
}
if (s == e) return s;
for (int i = 14; i >= 0; i--) {
if (pre[s][i] != pre[e][i]) {
s = pre[s][i];
e = pre[e][i];
}
}
return pre[s][0];
};
while (m--) {
cin >> s >> e;
cout << dist[s] + dist[e] - 2 * dist[lca(s, e)] << endl;
}
return 0;
}