Description

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

Analysis

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

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

• 老老实实从树上走；
• 从 s s s 走到一个关键点 k 1 k_1 k1​，穿越到另一个关键点 k 2 k_2 k2​，再走到 t t t。

第一种情况就是常规树上两点最短路。
第二种情况，根据贪心思想，选取的 k 1 , k 2 k_1,k_2 k1​,k2​ 一定是距离 s , t s,t s,t 最近的两个。所以我们初始时一次 bfs 求出每个点 i i i 到传送门的距离 d s t i dst_i dsti​，最终答案即为 d s t s + d s t t dst_s+dst_t dsts​+dstt​。

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  #include  #include  using namespace std;  using Graph = vector>; const int INF = 1e9;  struct LCA{     int n, k;     vector dep;     vector> 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(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 que;     vector 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; }