吉浦网站建设,wordpress 4.1分页,网络营销品牌策划,深圳网站建设信科便宜Description
给定一棵 n n n 个点的树#xff0c;每条边权值均为 1 1 1#xff0c;树上有 k k k 个关键点#xff0c;关键点们在 0 0 0 的时间内相互可达#xff0c; q q q 次询问#xff0c;求 s → t s\to t s→t 的最短路。
Analysis
考虑暴力建图#xff0c;…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−12n(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_sdst_t dstsdstt。
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 vectorvectorint;
const int INF 1e9;struct LCA{int n, k;vectorint dep;vectorvectorint 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, vectorint(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);queueint que;vectorint 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;
}
