信奥赛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输入 #15 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5输出 #14 4 1 4 4说明/提示对于30 % 30\%30%的数据N ≤ 10 N\leq 10N≤10M ≤ 10 M\leq 10M≤10。对于70 % 70\%70%的数据N ≤ 10000 N\leq 10000N≤10000M ≤ 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×1051 ≤ x , y , a , b ≤ N 1 \leq x, y,a ,b \leq N1≤x,y,a,b≤N不保证a ≠ b a \neq bab。样例说明该树结构如下第一次询问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。#includebits/stdc.husingnamespacestd;constintN5e510;// 最大节点数constintLOG20;// 最大对数深度2^20 500000intn,m,s;// 节点数、查询数、根节点vectorintg[N];// 邻接表存储树intd[N];// 每个节点的深度intf[N][LOG];// f[i][j]表示节点i向上跳2^j步到达的节点// BFS预处理深度和倍增数组voidbfs(introot){queueintq;q.push(root);d[root]1;// 根节点深度为1while(!q.empty()){intuq.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(intk1;kLOG;k){for(inti1;in;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(intkLOG-1;k0;k--){// 如果a跳2^k步后深度仍不小于b就跳if(d[f[a][k]]d[b]){af[a][k];}}// 如果此时a和b相同说明b就是a的祖先if(ab)returna;// a和b同时向上跳直到它们的父节点相同for(intkLOG-1;k0;k--){// 如果父节点不同就跳这样最后会停在LCA的下一层if(f[a][k]!f[b][k]){af[a][k];bf[b][k];}}// 此时a和b的父节点就是LCAreturnf[a][0];}intmain(){cinnms;// 读入树结构for(inti1;in-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各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}