P8805 [蓝桥杯 2022 国 B] 机房 题解

## 题意 给定一棵 $n$ 个结点的树，每个结点的入度/出度即为其权值。一条路径的长度定义为**经过所有结点的权值总和**（包括起始和终止结点）。 回答 $m$ 个询问，对于 $i=1,2,\dots,m$： - 结点 $u_i$ 和 $v_i$ 之间的最短路径长度是多少？ $1\le n,m\le 10^5$。 ## 分析 首先考虑最短路的方法，$\mathcal O(n^3+m)$ 的 Floyd 和 $\mathcal O(nm)$ 的 DFS 肯定不行。 树上的路径问题一般使用 LCA，没学过的可以先看[OI Wiki上的介绍](https://oi-wiki.org/graph/lca/)。本题解中 LCA 使用预处理 $\mathcal O(n\log n)$，查询 $\mathcal O(\log n)$ 的**倍增算法**。 思路很明确： - 预处理出从根结点开始，到每个结点 $u$ 的路径长度 $\mathrm{dis}_u$。根结点任意，但**必须与LCA所使用的根结点相同**。 - 对于一次查询 $u\to v$，令 $f=\mathrm{LCA}(u,v)$。 - 此时，$u\to v$ 的最短路径肯定是 $u\to f\to v$。 - $u\to f$ 的路径长度（不包括 $f$）为 $\mathrm{dis}_u-\mathrm{dis}_f$。 - $v\to f$ 的路径长度（不包括 $f$）为 $\mathrm{dis}_v-\mathrm{dis}_f$。 - 于是，答案为 $\mathrm{dis}_u-\mathrm{dis}_f+\mathrm{dis}_v-\mathrm{dis}_f+\mathrm{cost}(f)=\mathrm{dis}_u+\mathrm{dis}_v-2\mathrm{dis}_f+\mathrm{cost}(f)$。 **注意计算答案时不要忘记加上$f$的权值。** 由于所有权值的和为 $2(N-1)$，肯定不会爆 `int`，所以直接使用 `int` 即可。 ## 代码 [提交记录传送门](https://www.luogu.com.cn/record/98500834) 跑得挺快的，没开 `O2`，$10$ 个点总共 $807\text{ms}$。 ```cpp #include <cstdio> #include <vector> #define maxn 100005 using namespace std; vector<int> G[maxn]; int depth[maxn], fa[maxn][17]; // 2^17=131072 int dis[maxn]; #define cost(v) (int)G[v].size() void dfs(int v, int par) { int d = depth[v] + 1; fa[v][0] = par; for(int i=1; (1<<i)<d; i++) fa[v][i] = fa[fa[v][i - 1]][i - 1]; dis[v] += cost(v); for(int u: G[v]) if(u != par) { dis[u] = dis[v]; depth[u] = d; dfs(u, v); } } int lca(int u, int v) { if(depth[u] < depth[v]) u ^= v ^= u ^= v; int m = depth[u] - depth[v]; for(int i=0; m; i++, m>>=1) if(m & 1) u = fa[u][i]; if(u == v) return u; for(int i=__builtin_log2(depth[u]); i>=0; i--) if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; return fa[u][0]; } int main() { int n, q; scanf("%d%d", &n, &q); for(int i=1; i<n; i++) { int x, y; scanf("%d%d", &x, &y); G[--x].push_back(--y); G[y].push_back(x); } dfs(0, -1); while(q--) { int u, v; scanf("%d%d", &u, &v); int f = lca(--u, --v); printf("%d\n", dis[u] + dis[v] - 2 * dis[f] + cost(f)); } return 0; } ```