信奥赛C++提高组csp-s之倍增算法思想及应用之LCA
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数N , M , S N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N − 1 N-1N−1行每行包含两个正整数x , y x, yx,y，表示x xx结点和y yy结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M MM行每行包含两个正整数a , b a, ba,b，表示询问a aa结点和b bb结点的最近公共祖先。
输出格式
输出包含M MM行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例 #1
输入 #1
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5输出 #1
4 4 1 4 4说明/提示
对于30 % 30\%30%的数据，N ≤ 10 N\leq 10N≤10，M ≤ 10 M\leq 10M≤10。
对于70 % 70\%70%的数据，N ≤ 10000 N\leq 10000N≤10000，M ≤ 10000 M\leq 10000M≤10000。
对于100 % 100\%100%的数据，1 ≤ N , M ≤ 5 × 10 5 1 \leq N,M\leq 5\times10^51≤N,M≤5×105，1 ≤ x , y , a , b ≤ N 1 \leq x, y,a ,b \leq N1≤x,y,a,b≤N，不保证a ≠ b a \neq ba=b。
样例说明：
该树结构如下：
第一次询问：2 , 4 2, 42,4的最近公共祖先，故为4 44。
第二次询问：3 , 2 3, 23,2的最近公共祖先，故为4 44。
第三次询问：3 , 5 3, 53,5的最近公共祖先，故为1 11。
第四次询问：1 , 2 1, 21,2的最近公共祖先，故为4 44。
第五次询问：4 , 5 4, 54,5的最近公共祖先，故为4 44。
故输出依次为4 , 4 , 1 , 4 , 4 4, 4, 1, 4, 44,4,1,4,4。
#include<bits/stdc++.h>usingnamespacestd;constintN=5e5+10;// 最大节点数constintLOG=20;// 最大对数深度，2^20 > 500000intn,m,s;// 节点数、查询数、根节点vector<int>g[N];// 邻接表存储树intd[N];// 每个节点的深度intf[N][LOG];// f[i][j]表示节点i向上跳2^j步到达的节点// BFS预处理深度和倍增数组voidbfs(introot){queue<int>q;q.push(root);d[root]=1;// 根节点深度为1while(!q.empty()){intu=q.front();q.pop();// 遍历u的所有邻居节点for(intv:g[u]){if(d[v])continue;// 如果已经访问过，跳过d[v]=d[u]+1;// 子节点深度 = 父节点深度 + 1f[v][0]=u;// v向上跳1步(2^0)到达父节点uq.push(v);}}// 预处理倍增数组for(intk=1;k<LOG;k++){for(inti=1;i<=n;i++){// f[i][k] = i向上跳2^k步 = 先跳2^(k-1)步，再跳2^(k-1)步f[i][k]=f[f[i][k-1]][k-1];}}}// 求节点a和b的最近公共祖先intlca(inta,intb){// 确保a的深度不小于b，方便后续处理if(d[a]<d[b])swap(a,b);// 将a向上跳到与b同一深度for(intk=LOG-1;k>=0;k--){// 如果a跳2^k步后深度仍不小于b，就跳if(d[f[a][k]]>=d[b]){a=f[a][k];}}// 如果此时a和b相同，说明b就是a的祖先if(a==b)returna;// a和b同时向上跳，直到它们的父节点相同for(intk=LOG-1;k>=0;k--){// 如果父节点不同就跳，这样最后会停在LCA的下一层if(f[a][k]!=f[b][k]){a=f[a][k];b=f[b][k];}}// 此时a和b的父节点就是LCAreturnf[a][0];}intmain(){cin>>n>>m>>s;// 读入树结构for(inti=1;i<=n-1;i++){intu,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}// 预处理bfs(s);// 处理每个查询while(m--){inta,b;scanf("%d%d",&a,&b);printf("%d\n",lca(a,b));}return0;}功能分析
算法思路
使用倍增法求解LCA（最近公共祖先）问题。主要思想是通过预处理每个节点向上跳2 k 2^k2k步的节点，从而在查询时能够快速跳跃到目标位置。
核心算法
数据结构
g[N]：邻接表存储树结构d[N]：记录每个节点的深度f[N][LOG]：倍增数组，f[i][j]表示从节点i向上跳2 j 2^j2j步到达的节点
预处理阶段（BFS）
- 计算每个节点的深度
- 初始化
f[i][0]（直接父节点） - 使用动态规划填充倍增数组：
f[i][k] = f[f[i][k-1]][k-1]
查询阶段（LCA函数）
- 步骤1：将较深的节点向上跳到与另一节点同一深度
- 步骤2：如果此时两节点相同，直接返回
- 步骤3：两节点同时向上跳，直到它们的父节点相同
- 步骤4：返回父节点即为LCA
关键理解点
- 深度对齐：总是让较深的节点向上跳到与较浅节点同一深度
- 倍增跳跃：从最大步长(2^k)开始尝试，能跳就跳（不会跳过目标深度）
- 同时跳跃：深度对齐后，两个节点一起向上跳，但保持不跳到同一个节点（停在LCA的下一层）
- 父节点即LCA：最后a和b的父节点就是最近公共祖先
时间复杂度
- 预处理：O(n log n)
- 每次查询：O(log n)
- 总体：O((n + m) log n)，能够处理5×10 5 10^5105级别的数据
算法优势
- 查询效率高，适合多次查询的场景
- 代码实现相对简单
- 空间复杂度可控（O(n log n)）
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
)
