设 A(x) 为 x 到最近传送门的树上距离,答案 = min(树上距离, A(u) + A(v))。
小杨准备前往 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 的上限 |
|---|---|---|---|---|
| 1 | 30 | 500 | 500 | 1 |
| 2 | 30 | 2 × 10⁵ | 0 | 2 × 10⁵ |
| 3 | 40 | 2 × 10⁵ | 2 × 10⁵ | 2 × 10⁵ |
| 样例 | 内容 |
|---|---|
| 输入 #1 | 7 2 1 |
| 输出 #1 | 4 |
| 输入 #2 | 5 0 3 |
| 输出 #2 | 2 |
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(例如两端都是传送门) |
u ⇝ 某个门 ⇝ v,而 A(u)、A(v) 取的正是"到最近门"的距离,所以 A(u) + A(v) 已经是最省的了P,让每座传送门 bᵢ 与 P 之间连一条权为 0 的边。在新图里 P 到任意点 x 的距离恰好就是 A(x)。从 u 到 v 的最短路要么不经过 P(那就是 dist_T(u, v)),要么经过 P(那就是 A(u) + A(v)),没有第三种可能A( ) 能一次算完?把所有传送门一起当源点做一次 BFS(初始距离 0),这就是"多源 BFS",得到的就是"每个点到最近传送门"的距离,复杂度 O(n)n = 2 × 10⁵,如果树退化成一条链,递归 DFS 的栈深度就是 2 × 10⁵,几乎必然爆栈;用 queue 做 BFS 则完全安全O(n);倍增预处理 O(n log n);每次询问一次 LCA O(log n),共 O(q log n)。总量约 10⁷道路是 5–7、3–6、2–3、1–5、5–4、1–2;传送门在 7 号和 4 号城市。把以 1 号为根画出来:
1
+-- 5
| +-- 7 <-- 传送门
| +-- 4 <-- 传送门
+-- 2
+-- 3
+-- 6初始把 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
树上距离:3 → 2 → 1 → 5 → 7,共 4 条边 ⇒ dist_T = 4
走传送门:A(3) + A(7) = 4 + 0 = 4
两者取最小:min(4, 4) = 4
✅ 答案 4,与样例输出一致
| 城市 x | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| A(x) | 2 | 3 | 4 | 0 | 1 | 5 | 0 |
| 是否传送门 | 否 | 否 | 否 | 是 | 否 | 否 | 是 |
本题里两种方案恰好都等于 4,所以只看这一个样例是分辨不出"要不要和 A(u) + A(v) 取最小"的——这是本题最隐蔽的陷阱,看下一节。
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 → 5 | 3 | 不是最优 |
| 走传送门 | 2 → 1(1 步),传送到 6,6 → 5(1 步) | 2 | 最优 |
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
树上距离 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 是 n = 5、k = 0、q = 3,传送门那一行是空行,此时题目退化成"纯树上的两点距离"。
1 +-- 5 | +-- 2 | | +-- 3 | +-- 4
4 的父结点是 1,5 的父结点是 1
LCA(4, 5) = 1
距离 = dep[4] + dep[5] − 2 × dep[1] = 1 + 1 − 0 = 2
✅ 答案 2
LCA(1, 4) = 1
距离 = 0 + 1 − 0 = 1
✅ 答案 1
4 → 1 → 5 → 2 → 3,共 4 条边
LCA(4, 3) = 1;dep[4] = 1,dep[3] = 3
距离 = 1 + 3 − 0 = 4
✅ 答案 4
| 询问 | u | v | dep[u] | dep[v] | LCA | 树上距离 = 答案 |
|---|---|---|---|---|---|---|
| 1 | 4 | 5 | 1 | 1 | 1 | 2 |
| 2 | 1 | 4 | 0 | 1 | 1 | 1 |
| 3 | 4 | 3 | 1 | 3 | 1 | 4 |
n + 1 行是空行,如果按"读一整行再拆分"的写法很容易错位。scanf 直接读 k 个整数(k = 0 时循环一次都不执行,天然跳过空行),这样根本不用关心换行在哪里。一次多源 BFS 求出 A[ ] 表,再用 LCA 求树上距离,每次询问取 min,单次 O(log n)
P,让每座传送门与 P 之间连 0 权边,则 A(x) = dist(x, P)。从 u 到 v 的最短路要么不经过 P(dist_T(u, v)),要么经过(A(u) + A(v)),穷尽了全部可能,所以 min 就是答案。对每次询问都跑一次 0-1 BFS;或把 k 座传送门两两之间连 0 权边再求最短路
A[ ] 与询问毫无关系,一次算完就够。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 多源 BFS + 倍增 LCA | O(n + q log n) | ✅ 正确且最快,官方思路 |
| 每问一次 0-1 BFS | O(q · n) 约 4 × 10¹⁰ | ❌ 超时 |
| 传送门两两连 0 权边 | O(k²) 条边,最多 4 × 10¹⁰ | ❌ 建不出图、爆内存 |
第一行输入 n k q;随后 n − 1 行输入每条道路的 x y;再一行输入 k 个传送门编号(k = 0 时留空即可);最后 q 行每行输入 u v。程序会算出 A[ ] 表,并对每次询问比较两种方案。
点按钮开始 →
#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; }
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,直接相加会溢出,必须先判可用 |
n = 2 × 10⁵ 的链一定爆栈;② 把传送门两两连 0 权边:最多 4 × 10¹⁰ 条边,根本建不出来,正确做法是"合成一个点";③ k = 0 的空行读错,导致后面所有询问错位;④ 忘记 min(·, A[u] + A[v])(两个样例都查不出来,务必自造数据);⑤ A[u] + A[v] 在 k = 0 时是 2 × 10⁹,拿来和 dT 比之前要判掉无穷大。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
7 2 1 | 4 | 题面样例 1(两种方案恰好都是 4) |
5 0 3 | 2 1 4 | 题面样例 2:k = 0,退化为纯树上距离 |
6 2 1 | 2 | 传送门真的省时间:树上距离 3,走传送门只要 2(漏项会输出 3) |
2 2 1 | 0 | 两座城市都是传送门,直接传送,耗时 0 |
3 1 1 | 2 | 传送门在中间:A(1) + A(3) = 2 与树上距离 2 相同 |
4 2 1 | 1 | 链两端各一座传送门,但 A(2)+A(3) = 2 > 1,取树上距离 |
4 4 1 | 0 | 所有城市都有传送门 ⇒ 任意询问都是 0 |
A[ ] 吗?② 深度是迭代 BFS 求的吗?③ 每次都取了 min(·, A[u] + A[v]) 吗?④ k = 0 能正常读入吗?⑤ LOG 开到 19 了吗?k = 0),务必自己造一条"两端有传送门的长链"验证。n = 2 × 10⁵ 的链形树会爆栈,请用迭代 BFS。4 × 10¹⁰ 条边,正确抽象是"所有传送门合成一个点"。n + 1 行是空行;用 scanf 直接读 k 个整数最稳。k = 0 时 A[u] + A[v] = 2 × 10⁹,要先判断 A[u] < INF 再相加。O(n)O(n)LOG 层 × n 个点 = O(n log n),约 19 × 2 × 10⁵ ≈ 3.8 × 10⁶O(log n),q 次共约 2 × 10⁵ × 19 ≈ 3.8 × 10⁶10⁷ 级别邻接表存 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 白占内存。
// ---------- 技巧 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) 就会漏掉。)bᵢ 传到 b_{i+1}",还能用这一题的做法吗?(这时传送门之间成了一棵新的结构,"粘成一个点"的抽象不再成立,需要重新建模——先想清楚抽象的正确性,再动手写代码,才是这类题的关键。)