洛谷 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;
}