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