商人的总路程就是从首都出发后，相邻两站之间树上距离的总和；用倍增 LCA 快速求两点距离，再顺着给定路线累加即可。
OJ: luogu
题目 ID: P8855
难度:普及+/提高
标签:LCA倍增树形结构
日期: 2026-06-20 02:40
题意
给一棵树，首都编号为 1。
商人从首都出发，接下来要按给定顺序依次去若干个城镇做生意。
树上每条边的长度都是 1，要求输出：
- 按这个顺序走完全部行程的最短总时间
因为图本身是一棵树，所以任意两点之间路径唯一，最短时间其实就是：
- 从当前城市到下一个城市的树上距离
把这些相邻路段全部加起来。
样例图
样例树结构如下：
graph G {
1 -- 2;
1 -- 5;
5 -- 3;
5 -- 4;
}
路线是：
1 -> 3 -> 2 -> 5
对应路程分别是：
1 -> 3：23 -> 2：32 -> 5：2
总和就是 7。
思路
先看一个最直接的小数据暴力：
cpp
// brute.cpp：每次在树上直接找两点间的唯一路径长度，然后顺着路线累加。
// 这个做法最贴近题意，但每次都重新搜索路径，只适合小数据验证。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int n;
vector<int> g[MAXN];
int parent_arr[MAXN];
bool dfs_find(int u, int target, int fa) {
if (u == target) {
return true;
}
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa) {
continue;
}
parent_arr[v] = u;
if (dfs_find(v, target, u)) {
return true;
}
}
return false;
}
int dist(int u, int v) {
for (int i = 1; i <= n; i++) {
parent_arr[i] = 0;
}
dfs_find(u, v, 0);
int len = 0;
int x = v;
while (x != u) {
len++;
x = parent_arr[x];
}
return len;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
g[i].clear();
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int m;
cin >> m;
long long answer = 0;
int last = 1;
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
answer += dist(last, x);
last = x;
}
cout << answer << '\n';
return 0;
}暴力做法就是：
- 当前在
last - 下一站是
x - 直接在树上找出
last -> x的唯一路径长度 - 把所有相邻两站距离累加
这个方法很好理解，但如果每一段都重新搜路径，就会慢。
真正需要高效解决的，其实只有一个子问题：
- 如何快速求树上两点距离
这正是 LCA 的标准应用。
设两点为 u, v，它们的最近公共祖先为 p = lca(u, v)。
那么两点距离就是：
depth[u] + depth[v] - 2 * depth[p]
所以整道题分成两步：
- 预处理倍增 LCA
- 顺着给定路线，把相邻两站的距离加起来
由于商人从首都出发，所以初始位置直接设成：
last = 1
后面每读到一个目的地 x，就：
- 累加
dist(last, x) - 再令
last = x
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30000 + 5;
const int LOG = 16;
int n;
vector<int> g[MAXN];
int depth_arr[MAXN];
int up[MAXN][LOG];
void init_graph(int n) {
for (int i = 1; i <= n; i++) {
g[i].clear();
depth_arr[i] = 0;
for (int j = 0; j < LOG; j++) {
up[i][j] = 0;
}
}
}
void add_edge(int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
void build_lca(int root) {
vector<int> st;
st.push_back(root);
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (size_t i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == up[u][0]) {
continue;
}
up[v][0] = u;
depth_arr[v] = depth_arr[u] + 1;
for (int j = 1; j < LOG; j++) {
up[v][j] = up[up[v][j - 1]][j - 1];
}
st.push_back(v);
}
}
}
int kth_ancestor(int u, int k) {
for (int j = 0; j < LOG; j++) {
if (k & (1 << j)) {
u = up[u][j];
}
}
return u;
}
int lca(int a, int b) {
if (depth_arr[a] < depth_arr[b]) {
swap(a, b);
}
a = kth_ancestor(a, depth_arr[a] - depth_arr[b]);
if (a == b) {
return a;
}
for (int j = LOG - 1; j >= 0; j--) {
if (up[a][j] != up[b][j]) {
a = up[a][j];
b = up[b][j];
}
}
return up[a][0];
}
int dist(int a, int b) {
int p = lca(a, b);
return depth_arr[a] + depth_arr[b] - 2 * depth_arr[p];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
init_graph(n);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
build_lca(1);
int m;
cin >> m;
long long answer = 0;
int last = 1; // 商人从首都 1 出发。
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
answer += dist(last, x);
last = x;
}
cout << answer << '\n';
return 0;
}复杂度
预处理倍增祖先表：
每次求一段距离：
总共有 m 段行程，所以总复杂度：
空间复杂度：
总结
这题表面上是“商人走路线”，本质上只有一句话：
- 把整段路线拆成很多个相邻两站之间的树上距离
一旦看出这一点，后面就是标准模板：
- 倍增求 LCA
- 用深度算两点距离
- 顺序累加
所以它本质是一道很纯的：
LCA 求距离
的入门应用题。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
