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

Description

给定一棵 $n$ 个点的树，每条边权值均为 $1$，树上有 $k$ 个关键点，关键点们在 $0$ 的时间内相互可达，$q$ 次询问，求 $s\to t$ 的最短路。

Analysis

考虑暴力建图，则图上共有 $(n-1+\frac{n(n-1)}{2})$条边，在 $n,k$ 均为最大的情况下，图上共有大约 $2\times 10^{10}$ 条边，铁定 MLE。

我们注意到，从 $s$ 到 $t$ 只有两种情况：

• 老老实实从树上走；
• 从 $s$ 走到一个关键点 $k_1$，穿越到另一个关键点 $k_2$，再走到 $t$。

第一种情况就是常规树上两点最短路。
第二种情况，根据贪心思想，选取的 $k_1,k_2$ 一定是距离 $s,t$ 最近的两个。所以我们初始时一次 bfs 求出每个点 $i$ 到传送门的距离 $ds{t}_i$，最终答案即为 $ds{t}_s+ds{t}_t$。

Code

// Problem: P10289 [GESP样题 八级] 小杨的旅游
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10289
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <iostream>
#include <queue>
#include <cmath>
using namespace std;using Graph = vector<vector<int>>;
const int INF = 1e9;struct LCA{int n, k;vector<int> dep;vector<vector<int>> f;Graph G;LCA() {}LCA(const Graph &tree): G(tree){n = G.size();k = (int)log2(n) + 1;dep.assign(n, 0);f.assign(n, vector<int>(k, -1));dfs(0, 0);}void dfs(int u, int fa){dep[u] = dep[fa] + 1;f[u][0] = fa;for(int i = 1; i < k; i++) f[u][i] = f[f[u][i - 1]][i - 1];for(auto v: G[u]){if(v == fa) continue;dfs(v, u);}}int lca(int x, int y){if(dep[x] < dep[y]) swap(x, y);for(int i = k - 1; i >= 0; i--)if(dep[f[x][i]] >= dep[y]) x = f[x][i];if(x == y) return x;for(int i = k - 1; i >= 0; i --)if(f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}return f[x][0];}int dist(int x, int y){return dep[x] + dep[y] - 2 * dep[lca(x, y)];}};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, k, q;cin >> n >> k >> q;Graph G(n);for (int i = 0, u, v; i < n - 1; i++) {cin >> u >> v;u--, v--;G[u].push_back(v);G[v].push_back(u);}LCA tree(G);queue<int> que;vector<int> dis(n, INF);for (int i = 0, x; i < k; i++) {cin >> x;x--;que.push(x);dis[x] = 0;}while (que.size()) {int u = que.front();que.pop();for (auto v: G[u])if (dis[v] == INF) {dis[v] = dis[u] + 1;que.push(v);}}auto dist = [&](int x, int y) {return min(tree.dist(x, y), dis[x] + dis[y]);};for (int i = 0, u, v; i < q; i++) {cin >> u >> v;u--, v--;cout << dist(u, v) << endl;}return 0;
}