[GESP样题 八级] 小杨的旅游 题解

题目分析

小杨在一棵由 $n$ 个城市组成的树上游玩，城市间双向道路的通行时间为 $1$。有 $k$ 个城市设有传送门，从任意传送门可以花费 $0$ 时间传送到另一个传送门。小杨要进行 $q$ 次旅行，每次起点 $u_i$ 终点 $v_i$，求最短旅行时间。

由于树边权为 $1$，若不使用传送门，最短时间就是树上两点的距离。若使用传送门，则可以先去到某个传送门，传送到另一个传送门，再走到终点。因此我们的任务是快速求解两种方案的时间并取最小值。

解题思路

对于一次从 $u$ 到 $v$ 的旅行，有两种可能的最优方案：

1. 不借助传送门：直接沿树边行走。
   最短时间 = $dist(u, v) = depth[u] + depth[v] - 2 \times depth[lca(u, v)]$，其中 $lca(u,v)$ 是 $u$ 和 $v$ 的最近公共祖先，$depth$ 是以 $1$ 为根的深度（设根深度为 $1$ 或 $0$ 均可，不影响差值）。

2. 借助传送门：从 $u$ 走到某个传送门 $a$，花费 $dist(u, a)$，然后经传送门到 $b$（花费 $0$），再从 $b$ 走到 $v$，花费 $dist(b, v)$。
   为了最小化总时间，显然应选择离 $u$ 最近的传送门作为 $a$，离 $v$ 最近的传送门作为 $b$。令 $op[x]$ 表示城市 $x$ 到最近传送门的距离（若没有传送门可达则定义为无穷大），则借助传送门的最短时间为 $op[u] + op[v]$。
   注意：当 $k=0$（没有传送门）时，$op$ 全部无穷大，只能选择方案1。

最终答案即为 $\min(dist(u, v), op[u] + op[v])$。

因此，我们需要预处理两个信息：

• 任意两点的树上距离（通过 LCA 实现）。
• 每个节点到最近传送门的距离（多源 BFS）。

每次查询在 $O(\log n)$ 时间内回答即可。

算法说明

1. 树上距离与 LCA

使用倍增法求 LCA。

• 首先以 $1$ 为根进行 DFS，记录每个节点的深度 $dep$ 和向上 $2^i$ 级的祖先 $fa[x][i]$。
• 对于询问 $(u, v)$，通过比较深度将 $u, v$ 跳到同一深度，然后一起向上跳找到 LCA。
• 套用公式得到树上距离。

2. 最近传送门距离（多源 BFS）

因为边权均为 $1$，可以使用广度优先搜索（BFS） 同时从所有传送门出发，计算每个节点最近的传送门距离 $op$。

• 初始将所有传送门节点加入队列，距离设为 $0$。
• 其他节点距离初始化为 $-1$（或无穷大）。
• 进行 BFS，对于每个节点扩展邻居，若邻居未访问，则更新距离并入队。
• BFS 结束后，每个节点的 $op$ 值即为到最近传送门的最短距离。

3. 查询处理

对于每次查询 $(u, v)$：

• 计算 $lca = LCA(u, v)$，树上距离 $d1 = dep[u] + dep[v] - 2 \times dep[lca]$。
• 若 $op[u] \neq -1$ 且 $op[v] \neq -1$，则 $d2 = op[u] + op[v]$；否则 $d2$ 为一个非常大的数。
• 输出 $\min(d1, d2)$。

时间复杂度分析

• 建图：$O(n)$。
• DFS 预处理深度与倍增数组：$O(n \log n)$。
• 多源 BFS：每条边访问一次，$O(n)$。
• 每次 LCA 查询：$O(\log n)$。
• 总查询：$O(q \log n)$。
• 整体复杂度：$O((n + q) \log n)$，在 $n, q \le 2\times 10^5$ 时能够通过。

空间复杂度：邻接表、深度、父节点倍增数组、$op$ 数组等，均为 $O(n \log n)$。

参考代码

下面给出清晰规范的 C++ 实现，并附有详细注释。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 200100;
5const int INF = 0x3f3f3f3f;
6
7int n, k, q;
8vector<int> g[N];          // 邻接表
9int dep[N], fa[N][20];     // 深度和倍增父节点
10int op[N];                 // 到最近传送门的距离，-1 表示未计算/不可达
11
12// 深度优先搜索，处理深度和倍增数组
13void dfs(int u, int parent) {
14    fa[u][0] = parent;
15    dep[u] = dep[parent] + 1;
16    for (int i = 1; i <= 19; ++i) {
17        if (fa[u][i - 1])
18            fa[u][i] = fa[fa[u][i - 1]][i - 1];
19        else break;
20    }
21    for (int v : g[u]) {
22        if (v != parent) dfs(v, u);
23    }
24}
25
26// 求 LCA
27int lca(int x, int y) {
28    if (dep[x] < dep[y]) swap(x, y);
29    // 让 x 跳到和 y 同一深度
30    for (int i = 19; i >= 0; --i)
31        if (dep[fa[x][i]] >= dep[y])
32            x = fa[x][i];
33    if (x == y) return x;
34    // 一起向上跳
35    for (int i = 19; i >= 0; --i)
36        if (fa[x][i] != fa[y][i])
37            x = fa[x][i], y = fa[y][i];
38    return fa[x][0];
39}
40
41// 多源 BFS 计算最近传送门距离
42void bfs() {
43    queue<int> q;
44    memset(op, -1, sizeof(op));   // 初始化为 -1
45    // 读入传送门，并加入队列
46    for (int i = 0; i < k; ++i) {
47        int x; cin >> x;
48        op[x] = 0;
49        q.push(x);
50    }
51    while (!q.empty()) {
52        int u = q.front(); q.pop();
53        for (int v : g[u]) {
54            if (op[v] == -1) {    // 未访问过
55                op[v] = op[u] + 1;
56                q.push(v);
57            }
58        }
59    }
60}
61
62int main() {
63    ios::sync_with_stdio(false);
64    cin.tie(0);
65
66    cin >> n >> k >> q;
67    for (int i = 1; i < n; ++i) {
68        int u, v; cin >> u >> v;
69        g[u].push_back(v);
70        g[v].push_back(u);
71    }
72
73    // 预处理深度和 LCA
74    dfs(1, 0);
75    // 预处理最近传送门距离
76    bfs();
77
78    // 处理查询
79    while (q--) {
80        int u, v; cin >> u >> v;
81        int L = lca(u, v);
82        int d1 = dep[u] + dep[v] - 2 * dep[L]; // 树上距离
83        int d2 = INF;
84        if (op[u] != -1 && op[v] != -1)
85            d2 = op[u] + op[v];                // 传送距离
86        cout << min(d1, d2) << '\n';
87    }
88    return 0;
89}

代码解释

• 邻接表：使用 vector<int> g[N] 存储树边，简洁方便。
• DFS：从根节点 $1$ 开始递归，计算每个节点的深度 dep 和向上 $2^i$ 祖先 fa[u][i]。fa[u][0] 是直接父亲。
• LCA 查询：先将深度较大的节点上提至与另一个节点同深度，然后两节点同步上跳直到父节点相同。倍增使得每次跳跃的步长为 $2^i$，保证了 $O(\log n)$ 的时间。
• BFS：先将所有传送门节点入队，距离 op 设为 $0$。之后逐层扩展，未访问的邻居的距离等于当前节点距离 $+1$。由于边权为 $1$，BFS 保证距离最短。未访问到的节点维持 -1，表示没有传送门可达（本题中树连通，$k \ge 1$ 时所有节点均可达，但 $k=0$ 时需特殊判断）。
• 查询答案：树上距离 d1 直接根据深度和 LCA 计算；若两个端点都能到达传送门（op 不为 -1），则计算传送方案距离 d2 = op[u] + op[v]，否则将 d2 设为无穷大；取两者最小值输出。

细节提醒

• 当 $k = 0$ 时，bfs() 不执行任何入队操作，所有 op 保持 -1。查询时会自动跳过传送方案，仅输出树上距离。
• 无穷大设置建议使用 0x3f3f3f3f 或 1e9 等足够大但不溢出的值。
• 日志级数 $19$ 足够应对 $n \le 2\times 10^5$（$2^{19}=524288>200000$）。

至此，我们就能在 $O((n+q)\log n)$ 的时间内解决本题，并通过所有测试数据。