洛谷 P10289 [GESP样题 八级] 小杨的旅游 C++ 完整题解
一、题目链接
P10289 [GESP样题 八级] 小杨的旅游 - 洛谷
二、题目大意
n个节点之间有n - 1条边，其中k个节点是传送门，任意两个传送门之间可以 以0单位地时间相互到达。问从u到v至少需要多少时间？
三、解题思路
输入不必多讲。
cin >> n >> k >> q; for (int i = 1; i <= n - 1; i++) {int x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x); } for (int i = 1; i <= k; i++) cin >> door[i];BFS？DFS？
对于这个题目，你肯定会想到用DFS和BFS直接去做。
但
或者
当然了，更好的方法一定还有，本文只是介绍了一种方法。
正解
分成两种方案：使用传送门和不使用传送门，取快者。
使用传送门
用BFS找到每个节点离最近传送点的距离存入dst数组，结果就是：从起点走到最近传送点 -> 传送到离终点最近的传送点 -> 走到终点 dst[u] + dst[v]
int dst[N]; // dst[i] = i 到 离i最近的传送点 的距离void bfs() {memset(dst, 0x3f, sizeof (dst));queue<int> qu;for (int i = 1; i <= k; i++) {qu.push(door[i]); // 存入所有的传送点dst[door[i]] = 0;}while (!qu.empty()) {int now = qu.front();qu.pop();for (int x : e[now]) {if (dst[x] == 0x3f3f3f3f) {dst[x] = dst[now] + 1; // 更新x离最近传送点的位置qu.push(x);}}} } ... { ...bfs();int res1 = dst[u] + dst[v]; ... } ...不使用传送门
普通的BFS方法超时了，这里介绍一种可行的方法(LCA)
什么是LCA
LCA的意思是最近公共祖先，如下图，A与B的最近公共祖先是X。
如何用LCA计算A到B的距离
距离dist
首先计算每个节点离根的距离，也就是深度 - 1。
A与B的距离
= dist[A] + dist[B] - 2 * dist[x]
建立dist
int dist[N] = {-1}; // dist[0] = -1 dist[1]才能 = 0 void dfs(int fa, int x) {dist[x] = dist[fa] + 1;for (int u : e[x]) {if (u != fa) // 不能走回头路 省去vis数组dfs(x, u);} } ... { ...dfs(0, 1); // 起初给一个无意义的0作为根节点的父亲 ... } ...接着是lca函数：
int lca(int u, int v);lca函数中有两个工作要做
1. 把u和v的深度化作一样 循环上移u或者v，直到dist[u] == dist[v]
// 半伪代码 if (dist[u] > dist[v])swap(u, v); // 保证v更深 要不停更新v while (dist[u] < dist[v]) {v = v的父亲; } if (u == v) // 如果在没有更新 u 的情况下两者相等 那已经找到了最近公共祖先return u;2. u和v一起更新 直到两者相等就返回
// 半伪代码 while (u != v) {u = u的父亲;v = v的父亲; } return u;太慢了！！！
u 或者 v一层一层上去可没时间。
极端情况下就是这样：
每次处理数据都需要进行一次，假设q = 数据最大值，循环次数就是(2 * 100000) ^ 2 = 40,000,000,000。
使用倍增法优化
我们把u，v的第x个祖先看成2 ^ x + 2 ^ y + 2 ^ z...
int f[N][20]; // f[x][i] 节点 x 的 第2^i 个祖先(从下往上)DFS中记录下任意节点的第2 ^ i个祖先，如下（包含原本的代码）。
void dfs(int fa, int x) {dist[x] = dist[fa] + 1;f[x][0] = fa; // x的第2^0(1)个祖先就是它爹for (int i = 1; i <= 18; i++)f[x][i] = f[f[x][i - 1]][i - 1]; // x的第2^i个祖先就是 它2^(i-1)个祖先的第2^(i-1)个祖先 因为2^i = 2^(i-1) + 2^(i-1)for (int u : e[x]) {if (u != fa)dfs(x, u);} }LCA中也要改动。
int lca(int u, int v) {// 1if (dist[u] > dist[v])swap(u, v);for (int i = 18; i >= 0; i--) { // 2^18 > 2*10^5if (dist[u] <= dist[f[v][i]])v = f[v][i];if (u == v) return u;}//2for (int i = 18; i >= 0; i--) {if (f[u][i] != f[v][i])u = f[u][i], v = f[v][i];}return f[u][0]; // u和v最后是它们公共祖先的两个儿子 所以它们公共祖先是它们任意一个的父亲 }块1：i从18开始，试探v的第2^i个祖先 是否 存在 并 深度大于等于u，如果满足以上条件就把v变成v的第2^i个祖先，然后i = 17，16...继续试探，直到u == v或i == 0。
块2：i同样从18开始，试探v的第2^i个祖先 是否和 u的第2^i个祖先不相等，如果不相等，就更新u和v（同上），循环结束后，u和v一定是它们最近公共祖先的两个儿子，最后返回它们任意一个的父亲。
四、完整代码
长度有点小小的震撼，但相信你已经看懂了。
#include <iostream> #include <cstring> #include <queue> using namespace std;const int N = 200005;vector<int> e[N]; int n, k, q, door[N]; // door[] 存放每个传送点 int dist[N] = {-1}, f[N][20]; // dist[] 每个点离根节点的距离 f[x][i] 节点 x 的 第2^i 个祖先(从下往上) int dst[N]; // dst[i] = i 到 离i最近的传送点 的距离void bfs() {memset(dst, 0x3f, sizeof (dst));queue<int> qu;for (int i = 1; i <= k; i++) {qu.push(door[i]); // 存入所有的传送点dst[door[i]] = 0;}while (!qu.empty()) {int now = qu.front();qu.pop();for (int x : e[now]) {if (dst[x] == 0x3f3f3f3f) {dst[x] = dst[now] + 1; // 更新x离最近传送点的位置qu.push(x);}}} }void dfs(int fa, int x) {dist[x] = dist[fa] + 1;f[x][0] = fa;for (int i = 1; i <= 18; i++)f[x][i] = f[f[x][i - 1]][i - 1];for (int u : e[x]) {if (u != fa)dfs(x, u);} }int lca(int u, int v) {if (dist[u] > dist[v])swap(u, v);for (int i = 18; i >= 0; i--) {if (dist[u] <= dist[f[v][i]])v = f[v][i];if (u == v) return u;}for (int i = 18; i >= 0; i--) {if (f[u][i] != f[v][i])u = f[u][i], v = f[v][i];}return f[u][0]; }int solve(int u, int v) {// ** 使用传送门int res1 = dst[u] + dst[v]; // 找离起点最近的传送点 传送至 离终点最近的传送点// **不使用传送门int res2 = dist[u] + dist[v] - 2 * dist[lca(u, v)];return min(res1, res2); // 取小者 }int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> k >> q;for (int i = 1; i <= n - 1; i++) {int x, y;cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}for (int i = 1; i <= k; i++) cin >> door[i];bfs();dfs(0, 1);while (q--) {int u, v;cin >> u >> v;cout << solve(u, v) << endl;}return 0; }