最近公共祖先(LCA)本文介绍求最近公共祖先的四种方法 包括倍增 树链剖分 RMQ(欧拉序) Tarjan离线目录最近公共祖先(LCA)一.LCA定义二. 求LCA2.1 倍增法2.2 树链剖分2.3 RMQ (欧拉序)2.4 Tarjan离线2.5 一点小问题三. 总结一.LCA定义给定一棵树 以及树上两个节点 u, v 求它们的最近公共祖先 即深度最大且同时为 u, v 祖先的节点例题:洛谷P3379二. 求LCA2.1 倍增法关于倍增思想 参见倍增 及ST表RMQ思想:先预处理每个 u 向上跳 2k步到达的祖先 f[u][k]LCA:将深度较深的节点(图中u)向上跳到与另一个节点同深度(黄色节点)若节点相同 证明浅节点是二人的LCA 直接返回该节点否则 枚举 k 若 f[u][k] ! f[v][k] 则向上跳 2k步最终它们的父节点就是LCA即 先统一深度 再同时倍增跳跃voiddfs(intu,intf){// 预处理fa[u][0]f;// 当前节点向上1步为父节点// 倍增for(intk1;klg[n];k){fa[u][k]fa[fa[u][k-1]][k-1];}for(autov:g[u]){if(vf)continue;dep[v]dep[u]1;// 深度为父深度1dfs(v,u);}}// lcaintquery(intx,inty){if(dep[x]dep[y])swap(x,y);// x为深度深的intdisdep[x]-dep[y];//到达同深度所需距离for(intklg[n];k0;k--){// 即 深度差能被拆成多少个2^kif(dis(1k)){xfa[x][k];}}// 此时同深度if(xy)returnx;// 若节点相等 则找到了// 一起跳for(intklg[n];k0;k--){if(fa[x][k]!fa[y][k]){xfa[x][k];yfa[y][k];}}returnfa[x][0];}时间复杂度:预处理: n个节点 logn的循环 O(nlogn)查询: O(logn)关于lg[n] (即log数组):可参见倍增 及ST表RMQ文末2.2 树链剖分思想:将树划分为若干条重链让节点一次跳一条链几个概念:重儿子: 一个节点的所有儿子中 子树大小最大的那个儿子轻儿子: 除重儿子意外的其他儿子重边: 父节点连向重儿子的边轻边: 父节点连向轻儿子的边重链: 由重边连接成的链 (每个节点最多属一条重链 轻儿子自身作为链头从而开始新的重链)定义top[u]表示链头: u所在重链的顶端节点(深度最小的节点)预处理:两次dfs第一次: 计算父亲 深度 重儿子 子树大小voiddfs1(intu,intf){fa[u]f;// 父dep[u]dep[f]1;// 深度sz[u]1;// u为根子树大小son[u]0;// u的重儿子intmaxsize0;for(intv:g[u]){if(vf)continue;dfs1(v,u);sz[u]sz[v];if(sz[v]maxsize){maxsizesz[v];son[u]v;}}}第二次: 确定链头voiddfs2(intu,inttp){top[u]tp;if(son[u])dfs2(son[u],tp);// 递归重儿子for(intv:g[u]){if(vfa[u])continue;dfs2(v,v);// 轻儿子自己作为新链头}}LCA:当两个节点不在同一条重链上 让链头深度大的节点跳到它链头的父亲(跨过一条轻边) 直到两节点在同一条重链上 此时深度小的节点就是LCAintquery(intx,inty){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);// 此时x深度大xfa[top[x]];// 跳到链头的父亲}// 返回深度小的returndep[x]dep[y]?x:y;}时间复杂度:预处理n个节点 O(n)单次查询 两点最差最近祖先为根节点 从任意节点到根节点最多跳logn条链 故为O(logn)2.3 RMQ (欧拉序)欧拉遍历:对树进行dfs 每访问一个节点 (包括第一次进入和从子节点返回) 都记录一次该节点 得到一个序列 长度为 2(n-1)1 (一共n-1条边 每条边贡献两次访问 进入递归还要记录一次根节点)思想:两节点的LCA是欧拉序列中两节点第一次出现位置之间的最小深度节点因为从u到v的遍历过程必定经过它们的LCA欧拉序列中第一次出现 u 到第一次出现 v 的区间 包含了从 u 回溯到LCA再从LCA 到 v的完整路径路径上只有深度最小节点为二者共同的祖先明显 LCA就为这条路径的深度最小节点那么 问题就被转化为给定区间内求深度最小的节点然后,ST表解决RMQ问题(上文给了链接)定义几个数组:pos[u]: u第一次出现在欧拉序列中的下标euler[x]: 欧拉序列第t个节点dep[x]: 欧拉序列第t节点的深度欧拉数组的长度是2n 所以开的时候开2*N对于任意查询x,y设边界 l, r在深度数组对应区间找最小值下标idx答案为 euler[idx]预处理:voiddfs(intu,intfa,intdeep){pos[u]cnt;// 第一次出现位置euler[cnt]u;dep[cnt]deep;for(intv:g[u]){if(vfa)continue;dfs(v,u,deep1);euler[cnt]u;// 回溯时再次记录 udep[cnt]deep;}}// 最终cnt 2*n-1;ST表:intcmp(inta,intb){returndep[a]dep[b]?a:b;}voidbuild_st(){for(inti1;icnt;i)st[i][0]i;// 初始区间为 ifor(intj1;(1j)cnt;j){for(inti1;i(1j)-1cnt;i){//st表找区间最小值st[i][j]cmp(st[i][j-1],st[i(1(j-1))][j-1]);}}}LCA:intquery(intx,inty){intlpos[x],rpos[y];if(lr)swap(l,r);//正确规定左右边界// 查询intklg[r-l1];intidxcmp(st[l][k],st[r-(1k)1][k]);returneuler[idx];}时间复杂度:预处理ST表和dfs O(nlogn)查询 O(1)2.4 Tarjan离线思想:把查询数据离线储存 在一次dfs中同时处理所有查询 利用并查集维护当前已访问节点关系对于每一次询问 记(u, v, id) id为询问的编号步骤:对于节点 u 处理所有子节点v处理子节点之后 把v的并查集指向 u当 u 的所有子节点处理完毕 标记u为已访问遍历与 u 所有相关查询 (v, id)若 v 被访问过 那么find(v) 就为uv的LCA解释:当进行到第四步时 u的所有儿子处理完毕此时看一个查询 (u, v) 若v被访问过 那么v只会在两个地方:v在u 的某个子树中此时find(v) u LCA确实是u想象此时的 u 在某个根节点root的右子树 v可以在 root 的左子树里由于我们刚刚从左子树过来 v的并查集老大就是 root 那么find(v) root LCA确实是rootv在u的头上此时在处理 u , v是u的祖先且并查集仍指向自己 find(v) v 的确 是uv的LCA关于算法名Tarjan:跟强连通分量那个关系不大 这只是个人名 Tarjan这哥们很强发明了很多算法voidtarjan(intu,intfa){for(intv:g[u]){if(vfa)continue;tarjan(v,u);merge(u,v);//并查集操作 子树 v 合并到 u}//step3:vis[u]1;for(auto[v,id]:query[u]){if(vis[v]){ans[id]find(v);// 答案数组}}}!注意查询数组双向存储因为顺序不确定时间复杂度O(nq)2.5 一点小问题我们四种求LCA的预处理或统计答案用的都是dfs 当树为一条链的时候极易爆栈当 n1e5 时 就有可能爆了这里给出一个倍增法bfs防爆栈写法如果要用其他算法 那只能手写栈了voidbfs(intst){queueintq;q.push(st);dep[st]1;fa[st][0]0;while(!q.empty()){intuq.front();q.pop();for(autov:g[u]){if(vfa[u][0])continue;fa[v][0]u;dep[v]dep[u]1;for(intk1;klg[n];k){fa[v][k]fa[fa[v][k-1]][k-1];}q.push(v);}}}三. 总结方法预处理查询优点倍增O(nlogn)O(logn)通用 好理解树链剖分O(n)O(logn)常数小RMQO(nlogn)O(1)查询O(1)TarjanO(nq)离线复杂度最优