GESP 题解库 / 8 级题解 / [GESP样题 八级] 小杨的旅游 · 第 21 / 24 题
GESP样题 八级 · P10289 · 困难

小杨的旅游与传送门

设 A(x) 为 x 到最近传送门的树上距离,答案 = min(树上距离, A(u) + A(v))。

🚪
n, q ≤ 2 × 10⁵
城市数 / 旅游次数
🌲
0 ≤ k ≤ n
传送门数量(可为 0)
⚡
O(n + q log n)
多源 BFS + 倍增 LCA
🎯
min(树上距离, A(u)+A(v))
核心结论
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨准备前往 B 国旅游。

B 国有 n 座城市,这 n 座城市依次以 1 至 n 编号。城市之间由 n − 1 条双向道路连接,任意两座城市之间均可达(即任意两座城市之间存在可达的路径)。

小杨可以通过双向道路在城市之间移动,通过一条双向道路需要 1 单位时间。

B 国城市中有 k 座城市设有传送门。设有传送门的城市的编号依次为 b₁, b₂, …, b_k。小杨可以从任意一座设有传送门的城市花费 0 单位时间前往另一座设有传送门的城市。

注:如果两座设有传送门的城市之间存在双向道路,那么小杨可以选择通过双向道路移动,也可以选择通过传送门传送。

小杨计划在 B 国旅游 q 次。第 i 次旅游(1 ≤ i ≤ q),小杨计划从编号为 uᵢ 的城市前往编号为 vᵢ 的城市,小杨希望你能求出所需要的最短时间。

输入输出格式

项目说明
第一行三个正整数 n, k, q,分别表示城市数量、设有传送门的城市数量、旅游次数
接下来 n − 1 行每行两个正整数 xᵢ, yᵢ,表示一条双向道路连接的两座城市编号
第 n + 1 行k 个正整数,表示设有传送门的城市编号。当 k = 0 时这一行为空行
接下来 q 行每行两个正整数 uᵢ, vᵢ,表示第 i 次旅游的起点与终点
输出共 q 行,第 i 行输出一个非负整数,表示第 i 次旅游所需的最短时间
数据范围1 ≤ n ≤ 2 × 10⁵,0 ≤ k ≤ n,q ≤ 2 × 10⁵,uᵢ ≠ vᵢ

子任务

子任务分值n 的上限k 的上限q 的上限
1305005001
2302 × 10⁵02 × 10⁵
3402 × 10⁵2 × 10⁵2 × 10⁵

输入输出样例

样例内容
输入 #17 2 1
5 7
3 6
2 3
1 5
5 4
1 2
7 4
3 7
输出 #14
输入 #25 0 3
2 3
5 1
5 2
1 4
4 5
1 4
4 3
输出 #22
1
4
💡
人话翻译:先看清"图"长什么样:n 座城市 + n − 1 条边 + 任意两点可达 ⇒ 这是一棵树,而任意两点间的树上距离就是"只走路的答案"(每条边 1 单位时间)。

传送门的作用是"把 k 座城市粘成一个点":从任意一座传送门到任意另一座花 0 时间,所以它们完全等价。

于是从 u 到 v 的最短路只有两种形态:

  • 完全不用传送门:老老实实沿树走,代价 = dist_T(u, v);
  • 用一次传送门:先从 u 走到最近的传送门(代价 A(u)),传送过去(代价 0),再从某座传送门走到 v(代价 A(v)),合计 A(u) + A(v)。

答案就是这两者取最小。注意:"用两次以上传送门"不会更优——因为 A( ) 本身已经是"到最近传送门"的最短距离,再传一次只是原地兜圈。

🔍 关键词提取

树上的最短路多源 BFS倍增 LCA虚拟超级源点迭代预处理防爆栈

已知条件

项目说明
图的形态n 个点、n − 1 条边的连通无向图 ⇒ 树
边权每条边耗时 1(无向,两个方向都可以走)
传送门k 座城市设门,任意两门之间耗时 0
数据范围n ≤ 2 × 10⁵,q ≤ 2 × 10⁵,0 ≤ k ≤ n
退化情形k = 0 时传送门那一行是空行,答案就是纯树上距离
输出每次询问一行非负整数;uᵢ ≠ vᵢ,但答案仍可能是 0(例如两端都是传送门)

需要解决的问题

02
思维导图
整理解题思路的全貌
🚪 多源 BFS 求 A[ ] + 倍增 LCA 求树上距离,两者取最小
🧠 关键观察
传送门之间 0 时间 ⇒ 全部等价
A(x) = x 到最近传送门的距离
答案 = min(树上距离, A(u) + A(v))
用两次以上传送不会更优
🌊 多源 BFS
所有传送门当源点,距离先置 0
全部一次性入队
一次 BFS 得到整张 A[ ] 表
k = 0 时 A[ ] 全是无穷大
🌲 倍增 LCA
迭代 BFS 求深度,防爆栈
dep[u] + dep[v] − 2 × dep[LCA]
每次询问 O(log n)
up 表用 int 就够,省内存
⚠️ 易错点
递归 DFS 求深度 → 栈溢出
把传送门两两连边 → k² 条边建不出
k = 0 时那一行是空行,读入错位
忘记与 A(u) + A(v) 取最小
03
样例手算推导
样例 1 手算 + 一个"传送门真的省时间"的自造例子

🧮 样例 1:7 座城市、2 座传送门

道路是 5–7、3–6、2–3、1–5、5–4、1–2;传送门在 7 号和 4 号城市。把以 1 号为根画出来:

1
+-- 5
|   +-- 7   <-- 传送门
|   +-- 4   <-- 传送门
+-- 2
    +-- 3
        +-- 6
1
第一步:多源 BFS 求 A[ ]

初始把 7 与 4 的距离都设为 0,一起入队

从 7 出发:A(5) = 1

从 4 出发:A(5) 已经是 1,不再更新

继续扩展:A(1) = 2(1–5–7 或 1–5–4)

再往外:A(2) = 3、A(3) = 4、A(6) = 5

✅ A 表算完:A(1)=2,A(2)=3,A(3)=4,A(4)=0,A(5)=1,A(6)=5,A(7)=0

2
第二步:回答询问 3 → 7

树上距离:3 → 2 → 1 → 5 → 7,共 4 条边 ⇒ dist_T = 4

走传送门:A(3) + A(7) = 4 + 0 = 4

两者取最小:min(4, 4) = 4

✅ 答案 4,与样例输出一致

📊 A 表与两种方案

城市 x1234567
A(x)2340150
是否传送门否否否是否否是

本题里两种方案恰好都等于 4,所以只看这一个样例是分辨不出"要不要和 A(u) + A(v) 取最小"的——这是本题最隐蔽的陷阱,看下一节。

🔑
多源 BFS 的写法要点:把所有传送门的距离先设成 0、一起入队,然后再开始 BFS。
这样每个点第一次被访问时距离就是"到最近传送门的最短距离",整张表 O(n) 一次算完;k = 0 时队列为空,A[ ] 保持为无穷大,"第二种方案"自动作废。

🧮 一个必须自己造的例子:传送门真的省时间

样例 1 的两种方案恰好相等、样例 2 干脆没有传送门,所以"只输出树上距离"的程序能把两个样例全部骗过。必须自己造一个"传送门真的省时间"的数据。

取一条 6 个点的链 1–2–3–4–5–6,传送门放在两端 1 和 6,询问 2 → 5:

1 - 2 - 3 - 4 - 5 - 6
*                   *        (* 表示有传送门)
方案怎么走耗时是否正确
只走树2 → 3 → 4 → 53不是最优
走传送门2 → 1(1 步),传送到 6,6 → 5(1 步)2最优
1
算一算 A 表

A(1) = 0,A(6) = 0

A(2) = 1,A(5) = 1(都紧挨着一座传送门)

A(3) = 2,A(4) = 2

A(2) + A(5) = 1 + 1 = 2

2
两种方案取最小

树上距离 dist_T(2, 5) = 3

传送门方案 = A(2) + A(5) = 2

min(3, 2) = 2

✅ 答案 2(若漏掉第二项会输出 3)

⚠️
这就是本题最容易丢分的地方:两个样例都无法检验"有没有写 min(·, A[u] + A[v])"——样例 1 两种方案恰好都是 4,样例 2 是 k = 0。
先别急着提交,把上面这条链跑一遍:正确答案是 2,漏掉传送门项的程序会输出 3。

🧮 样例 2:k = 0 的退化情形

样例 2 是 n = 5、k = 0、q = 3,传送门那一行是空行,此时题目退化成"纯树上的两点距离"。

1
+-- 5
|   +-- 2
|   |   +-- 3
|   +-- 4
1
询问 4 → 5

4 的父结点是 1,5 的父结点是 1

LCA(4, 5) = 1

距离 = dep[4] + dep[5] − 2 × dep[1] = 1 + 1 − 0 = 2

✅ 答案 2

2
询问 1 → 4

LCA(1, 4) = 1

距离 = 0 + 1 − 0 = 1

✅ 答案 1

3
询问 4 → 3

4 → 1 → 5 → 2 → 3,共 4 条边

LCA(4, 3) = 1;dep[4] = 1,dep[3] = 3

距离 = 1 + 3 − 0 = 4

✅ 答案 4

📊 三个询问的汇总

询问uvdep[u]dep[v]LCA树上距离 = 答案
1451112
2140111
3431314
🔑
k = 0 时读入要小心:第 n + 1 行是空行,如果按"读一整行再拆分"的写法很容易错位。
最稳的写法是:用 scanf 直接读 k 个整数(k = 0 时循环一次都不执行,天然跳过空行),这样根本不用关心换行在哪里。
04
解法对比
多源 BFS + 倍增 LCA vs 每问一次 0-1 BFS vs 传送门两两连边

⚔️ 解法对比

🟢 多源 BFS + 倍增 LCA(推荐) 推荐

一次多源 BFS 求出 A[ ] 表,再用 LCA 求树上距离,每次询问取 min,单次 O(log n)

  • 预处理 O(n)
  • 每次询问 O(log n)
  • 代码约 70 行
  • 官方题解即此思路
💡
正确性来源:加一个虚拟点 P,让每座传送门与 P 之间连 0 权边,则 A(x) = dist(x, P)。从 u 到 v 的最短路要么不经过 P(dist_T(u, v)),要么经过(A(u) + A(v)),穷尽了全部可能,所以 min 就是答案。

🟠 每问一次 BFS / 传送门两两连边

对每次询问都跑一次 0-1 BFS;或把 k 座传送门两两之间连 0 权边再求最短路

  • 每问一次 BFS:O(q · n) ≈ 4 × 10¹⁰
  • 两两连边:O(k²) 条边,最多 4 × 10¹⁰ 条
  • 样例都能过,大数据必挂
  • 稍不注意就 MLE / TLE
⚠️
它们为什么会挂:传送门之间的连接是"完全图",根本没法真的建出来;正确的抽象是"所有传送门合成一个点",这才是题目的本质。
而每次询问重跑最短路则纯属浪费:A[ ] 与询问毫无关系,一次算完就够。

📈 性能对比

方案复杂度结论
多源 BFS + 倍增 LCAO(n + q log n)✅ 正确且最快,官方思路
每问一次 0-1 BFSO(q · n) 约 4 × 10¹⁰❌ 超时
传送门两两连 0 权边O(k²) 条边,最多 4 × 10¹⁰❌ 建不出图、爆内存
05
算法流程图
多源 BFS 求 A[ ] + LCA 求距离 + 取最小 主流程
开始读入 n、k、q 与 n − 1 条边,建无向邻接表读入 k 个传送门编号,全部入队并令 A[传送门] = 0多源 BFS 的队列还是空的吗?取出队首 x,用 A[x] + 1 去松弛每个邻居 y,必要时入队从 1 号城市迭代 BFS 求深度,填 up[x][0],再做倍增预处理循环:处理第 i 次旅游(i = 1 … q)读入 u、v,用 LCA 求树上距离 dist_T答案 = min(dist_T, A[u] + A[v]),输出答案q 次旅游全部回答完毕下一次旅游
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🚪 旅游最短时间推演器(多源 BFS + LCA)

第一行输入 n k q;随后 n − 1 行输入每条道路的 x y;再一行输入 k 个传送门编号(k = 0 时留空即可);最后 q 行每行输入 u v。程序会算出 A[ ] 表,并对每次询问比较两种方案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(多源 BFS + 迭代倍增 LCA)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const int LOG  = 19;               // 2^18 = 262144 > 2 * 10^5
const int INF  = 1000000000;

int n, k, q;
vector<int> g[MAXN];
int dep[MAXN], up[MAXN][LOG];
int A[MAXN];                       // A[x] = x 到最近传送门的树上距离

int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int d = dep[a] - dep[b];
    for (int j = 0; j < LOG; j++)
        if ((d >> j) & 1) a = up[a][j];
    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 main() {
    scanf("%d %d %d", &n, &k, &q);
    for (int i = 1; i < n; i++) {
        int x, y; scanf("%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
    }

    // (1) 多源 BFS:所有传送门当源点,一次求出 A[]
    for (int i = 1; i <= n; i++) A[i] = INF;
    queue<int> qu;
    for (int i = 0; i < k; i++) {
        int b; scanf("%d", &b);        // k = 0 时循环不执行,天然跳过空行
        A[b] = 0;
        qu.push(b);
    }
    while (!qu.empty()) {
        int x = qu.front(); qu.pop();
        for (int t = 0; t < (int)g[x].size(); t++) {
            int y = g[x][t];
            if (A[x] + 1 < A[y]) { A[y] = A[x] + 1; qu.push(y); }
        }
    }

    // (2) 迭代 BFS 求深度并填 up[x][0](千万别用递归 DFS)
    for (int j = 0; j < LOG; j++) up[1][j] = 1;      // 根指向自己
    vector<char> vis(n + 1, 0);
    queue<int> q2;
    q2.push(1); vis[1] = 1; dep[1] = 0;
    while (!q2.empty()) {
        int x = q2.front(); q2.pop();
        for (int t = 0; t < (int)g[x].size(); t++) {
            int y = g[x][t];
            if (!vis[y]) {
                vis[y] = 1;
                dep[y]   = dep[x] + 1;
                up[y][0] = x;
                q2.push(y);
            }
        }
    }
    for (int j = 1; j < LOG; j++)
        for (int x = 1; x <= n; x++)
            up[x][j] = up[up[x][j - 1]][j - 1];

    // (3) 回答询问
    while (q--) {
        int u, v; scanf("%d %d", &u, &v);
        int dT = dep[u] + dep[v] - 2 * dep[lca(u, v)];   // 方案一:全程走树
        int ans = dT;
        if (A[u] < INF && A[v] < INF)                    // k = 0 时 A 全是 INF
            ans = min(ans, A[u] + A[v]);                 // 方案二:走树 + 传送
        printf("%d\n", ans);
    }
    return 0;
}
🔑
四个要点:① 多源 BFS 要把所有传送门先设 0 再一起入队;② k = 0 时空行不用特殊处理——用 scanf 读 k 个整数,循环天然不执行;③ 深度用迭代 BFS 求,n = 2 × 10⁵ 的链用递归 DFS 会爆栈;④ 别忘了 min(·, A[u] + A[v]) 这一项(两个样例都无法替你检验它)。

📖 关键几行怎么看

代码作用为什么这样写
A[b] = 0; qu.push(b);多源 BFS 的初始化所有传送门同时当源点,一次 BFS 就得到"到最近门"的距离
if (A[x] + 1 < A[y])逐层松弛每个点最多入队一次,整张表 O(n)
for (int j = 0; j < LOG; j++) up[1][j] = 1;根的祖先指向自己倍增多跑几层也不会越界,比较时语义统一
dep[u] + dep[v] - 2 * dep[lca(u, v)]树上两点距离LCA 的标准用法:两边各自到 LCA 的距离之和
if (A[u] < INF && A[v] < INF)处理 k = 0没有传送门时 A[ ] 全是 INF,直接相加会溢出,必须先判可用
⚠️
五个坑:① 递归 DFS 求深度:n = 2 × 10⁵ 的链一定爆栈;② 把传送门两两连 0 权边:最多 4 × 10¹⁰ 条边,根本建不出来,正确做法是"合成一个点";③ k = 0 的空行读错,导致后面所有询问错位;④ 忘记 min(·, A[u] + A[v])(两个样例都查不出来,务必自造数据);⑤ A[u] + A[v] 在 k = 0 时是 2 × 10⁹,拿来和 dT 比之前要判掉无穷大。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
7 2 1
5 7
3 6
2 3
1 5
5 4
1 2
7 4
3 7
4题面样例 1(两种方案恰好都是 4)
5 0 3
2 3
5 1
5 2
1 4
4 5
1 4
4 3
2
1
4
题面样例 2:k = 0,退化为纯树上距离
6 2 1
1 2
2 3
3 4
4 5
5 6
1 6
2 5
2传送门真的省时间:树上距离 3,走传送门只要 2(漏项会输出 3)
2 2 1
1 2
1 2
1 2
0两座城市都是传送门,直接传送,耗时 0
3 1 1
1 2
2 3
2
1 3
2传送门在中间:A(1) + A(3) = 2 与树上距离 2 相同
4 2 1
1 2
2 3
3 4
1 4
2 3
1链两端各一座传送门,但 A(2)+A(3) = 2 > 1,取树上距离
4 4 1
1 2
2 3
3 4
1 2 3 4
1 4
0所有城市都有传送门 ⇒ 任意询问都是 0
✅
自查清单:① 是多源 BFS 求的 A[ ] 吗?② 深度是迭代 BFS 求的吗?③ 每次都取了 min(·, A[u] + A[v]) 吗?④ k = 0 能正常读入吗?⑤ LOG 开到 19 了吗?

🚨 易错点清单

⚠️
忘记与 A(u) + A(v) 取最小:两个样例都查不出来(样例 1 两方案相同、样例 2 是 k = 0),务必自己造一条"两端有传送门的长链"验证。
⚠️
递归 DFS 求深度:n = 2 × 10⁵ 的链形树会爆栈,请用迭代 BFS。
⚠️
把传送门两两连边:最多 4 × 10¹⁰ 条边,正确抽象是"所有传送门合成一个点"。
⚠️
k = 0 时读入错位:第 n + 1 行是空行;用 scanf 直接读 k 个整数最稳。
⚠️
无穷大参与相加:k = 0 时 A[u] + A[v] = 2 × 10⁹,要先判断 A[u] < INF 再相加。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n + q log n)
空间复杂度
O(n log n)
多源 BFS
O(n)
每次询问
O(log n)

时间怎么算的?

空间都用在哪?

邻接表存 2(n − 1) 条边,O(n);up[MAXN][19] 用 int 存约 2 × 10⁵ × 19 × 4 B ≈ 15 MB;A[MAXN] 与 dep[MAXN] 各 O(n)。整体约 20 MB,远低于常见 128 MB / 256 MB 限制。

✅ 总量约 10⁷ 次操作,2 × 10⁵ 规模下 1 秒内轻松跑完。注意两点:LOG 要开到 19(2¹⁸ = 262144 > 2 × 10⁵);倍增表用 int 就够,别开 long long 白占内存。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ---------- 技巧 1:多源 BFS 模板 ----------
const int INF = 1e9;
int A[MAXN];
for (int i = 1; i <= n; i++) A[i] = INF;
queue<int> qu;
for (int i = 0; i < k; i++) {          // 所有源点:距离先置 0,一起入队
    scanf("%d", &b);
    A[b] = 0;
    qu.push(b);
}
while (!qu.empty()) {
    int x = qu.front(); qu.pop();
    for (int y : g[x])
        if (A[x] + 1 < A[y]) { A[y] = A[x] + 1; qu.push(y); }
}

// ---------- 技巧 2:迭代求深度 + 倍增(防爆栈)----------
const int LOG = 19;
for (int j = 0; j < LOG; j++) up[1][j] = 1;   // 根指向自己
queue<int> q2; q2.push(1); vis[1] = 1;
while (!q2.empty()) {                          // 绝不用递归 DFS
    int x = q2.front(); q2.pop();
    for (int y : g[x]) if (!vis[y]) {
        vis[y] = 1; dep[y] = dep[x] + 1; up[y][0] = x; q2.push(y);
    }
}
for (int j = 1; j < LOG; j++)
    for (int x = 1; x <= n; x++) up[x][j] = up[up[x][j-1]][j-1];

// ---------- 技巧 3:两点树上距离 ----------
int dist_T(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

// ---------- 本题的收尾 ----------
// ans = min(dist_T(u, v), A[u] + A[v])
// "所有传送门等价" == "全部粘到同一个虚拟点 P 上"
// A(x) 就是 x 到 P 的距离,两类路径穷尽了全部可能

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
多源 BFS一次求出每点到最近传送门的距离多起点的最短路 / 多仓库到各点的距离
虚拟超级源点把所有传送门粘成一个点,抽象成"到 P 的距离""多个点两两 0 代价互通"的一切最短路问题
迭代 LCA 预处理用 BFS 代替递归 DFS 求深度一切 n ≥ 10⁵ 的树上问题(防栈溢出)
树上两点距离dep[u] + dep[v] − 2 × dep[LCA]树上路径长度、树上路径查询的基础工具
两种方案取最小"不用特殊边"与"用一次特殊边"分别计算带优惠 / 带瞬间移动的路径问题通用套路
🌟
思考题:如果传送门规则改成"每传送一次要花 1 单位时间",答案会变成什么?(提示:仍然只有"不用门"和"用一次门"两类最优形态,所以答案是 min(dist_T(u, v), A(u) + A(v) + 1)——注意多出来的那个 +1 是"传送本身的开销",把它写成 A(u) + A(v) 就会漏掉。)
再想一层:如果传送门不是零散分布,而是"任意两座传送门之间 0 时间"改成"只能从 bᵢ 传到 b_{i+1}",还能用这一题的做法吗?(这时传送门之间成了一棵新的结构,"粘成一个点"的抽象不再成立,需要重新建模——先想清楚抽象的正确性,再动手写代码,才是这类题的关键。)