【板子】LCA+ST

#include iostream #include vector #include algorithm using namespace std; const int MAXN 5e5 10; const int LOG 20; vectorint g[MAXN]; int up[LOG][MAXN]; // up[k][u] u跳2^k步祖先 int dep[MAXN]; // 每个点深度 int n, m, root; // dfs预处理深度与2^0祖先父节点 void dfs(int u, int fa) { up[0][u] fa; for (int i 1; i LOG; i) up[i][u] up[i-1][up[i-1][u]]; for (int v : g[u]) { if (v ! fa) { dep[v] dep[u] 1; dfs(v, u); } } } // 求a,b最近公共祖先 int lca(int a, int b) { // 保证a更深 if (dep[a] dep[b]) swap(a, b); // a向上跳到和b同深度 int d dep[a] - dep[b]; for (int i 0; i LOG; i) if (d (1 i)) a up[i][a]; if (a b) return a; // 同步往上跳直到LCA下一层 for (int i LOG-1; ~i; --i) { if (up[i][a] ! up[i][b]) { a up[i][a]; b up[i][b]; } } return up[0][a]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m root; for (int i 1, x, y; i n; i) { cin x y; g[x].push_back(y); g[y].push_back(x); } dep[root] 0; dfs(root, root); // 根的父亲设自己防越界 while (m--) { int a, b; cin a b; cout lca(a, b) \n; } return 0; }分步讲解1. 数组说明g[]邻接表存树up[k][u]倍增核心节点 u 向上跳 \(2^k\) 条边到达的祖先dep[u]节点 u 的深度根深度设为 0LOG20\(2^{20}1048576\)覆盖最大 \(5\times10^5\) 节点2. dfs 预处理初始化 \(up[0][u]\) 为 u 的直接父节点递推预处理所有 \(2^k\) 祖先up[i][u] up[i-1][ up[i-1][u] ]递归遍历子节点更新子节点深度并继续 dfs。3. LCA 核心流程拉平深度把深度更深的点向上跳直到两点深度相同特判相等拉平后两点相同该点就是 LCA同步上跳从最大幂次往下枚举若两点祖先不同则一起跳循环结束后两点的父节点即为 LCA。4. 输入输出加速ios::sync_with_stdio(false); cin.tie(nullptr);大数据必加关闭 cin 与 stdio 同步大幅提速输出用\n而非endlendl 会强制刷新缓冲区很慢。复杂度预处理\(O(N\log N)\)单次查询\(O(\log N)\) 适合本题多组询问场景。