【数据结构】浅谈倍增求LCA

思路

运用树上倍增法可以高效率地求出两点x,y的公共祖先LCA

我们设f[x][k]表示x的2^k辈祖先

f[x][0]为x的父节点

因为从x向根节点走2^k 可以看成从x走2^k-1步 再走2^k-1步

所以对于1≤k≤logn 有f[x][k]=f[f[x][k-1]][k-1] （类似二分思想）

预处理：

因此我们可以对树进行遍历后得到所有f[x][0] 再计算出f数组的所有值

求LCA：

设dep[x]为x的深度 设dep[x]≥dep[y]（否则 可以交换x和y）

使用二进制拆分 把x和y调整到同一深度

若此时x与y相等 则已经找到LCA

若不相等 则x和y同时向上跳同一深度 直到他们的父节点相同 则他们的父节点就是LCA

 代码

#include<iostream> #include<cstdio> #include<cmath> using namespace std; #define maxn 500050 #define INF 1e9+7 int n,m,cnt,ans,a,b,k,x,y; int h[maxn],dep[maxn],f[maxn][30]; struct Edge { int next; int to; }e[maxn<<1]; void add(int u,int v) { e[++cnt].to=v; e[cnt].next=h[u]; h[u]=cnt; } void deal(int u,int fa) { dep[u]=dep[fa]+1;//子节点深度等于父节点+1 for(int i=1;i<=21;i++) { f[u][i]=f[f[u][i-1]][i-1];//计算u的2^k辈祖先 } for(int i=h[u];i;i=e[i].next) { int v=e[i].to; if(v==fa) continue;//如果是父节点就退出 f[v][0]=u;//v是u的子节点 deal(v,u); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y);//如果x的深度比y小 就交换 for(int i=21;i>=0;i--)//从大到小循环 先走大步 如果不行在走小步 { if(dep[f[x][i]]>=dep[y]) x=f[x][i];//当走完深度还是大于y 就走 if(x==y) return x;//当x=y时 找到LCA } for(int i=21;i>=0;i--)//此时x和y已经在同一层了 { if(f[x][i]!=f[y][i])//如果往上走之后还没有到LCA 就往上走 { x=f[x][i]; y=f[y][i]; } } return f[x][0];//返回LCA } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x);//无向图 } deal(1,0);//预处理 for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); printf("%d\n",lca(x,y)); } }

 

转载于:https://www.cnblogs.com/BrokenString/p/9775540.html

相关资源：IOI国家集训队论文集1999-2019