问题描述
在一棵树中,如果某个节点z是节点x的祖先(即节点z深度<节点x),也是y的祖先。那么称节点z是x与y的公共祖先。
那顾名思义,所谓最近公共祖先,就是对于x和y来说距离之和最近的公共祖先。
解法一:向上标记法
除非你发了高烧啥都不会打,否则换方法
从x节点向上走到根节点,把所有经过的节点标记。
从y节点向上走,第一次遇到被标记过的节点的时候,该节点为所求点。
每次询问,最坏复杂度为O(n)
解法二:树上倍增法
不温不火,很适合考场的时候打啊…
首先理解倍增算法。类似于动态规划思想
复杂度O((n+m)log n)
倍增预处理
设F[x,k]表示x的2k辈祖先。也就是,x向上跳2k所到达的节点。如果跳到了一个压根不存在的节点,我们让他的值为0。
显然根据定义,可以得出F[x,0]就是x的父节点。
为了不少跳,求出k的范围应当属于[1,logn]。在c++中,应写为
t=(int)log(n)/log(2)+1
接下来就有转移方程:
F[x,k]=F[F[x,k-1],k-1] ,因为 2k-1+2k-1=2* 2k-1=2k
预计需要的时间复杂度O(n logn)
void bfs(){ q.push(1); d[1]=1; while(q.size()){ int x=q.front();q.pop(); for(int i=Head[x];i;i=Next[i]){ int y=End[i]; if(d[y]) continue; d[y]=d[x]+1; f[y][0]=x; for(int j=1;j<=t;j++){ f[y][j]=f[f[y][j-1]][j-1]; } q.push(y); } } }
跳跃式处理LCA
由上面的预处理,我们得到了已经初始化的D(深度)数组和F(倍增)数组
我们假定D[x]>=D[y] (否则你就交换一下嘛)
1.让x往上跳,先跳到和y一样高再说
怎么实现呢?枚举。枚举上跳步数。枚举jump=2logn一直枚举到20。为什么要倒着呢?因为要尽可能跳的次数少一点降低复杂度。
检查即将上跳到的节点是否比y要低一点。如果是就完成上跳,即让x=F[x,jump]
2.如果发现仅仅完成第一步就有了x==y(x跳到y脸上去了),说明y本来就是x的祖先,那么LCA就等于y。
3.让x和y一起往上跳,保持两者深度相同但不相汇。依然按照步骤一一样去枚举jump。只要F[x,jump]不等于F[y,jump],就赋值起跳。
4.经过了步骤3的磨砺,x和y一定就差最后一步就可以相汇了。那么两者任意一个节点的父节点就必然是LCA(x,y)。所以此时LCA(x,y)=F[x,0]
int lca(int x,int y){ if(d[x]>d[y]) swap(x,y); for(int i=t;i>=0;i--){ if(d[f[y][i]]>=d[x]) y=f[y][i]; if(x==y) return x; } for(int i=t;i>=0;i--){ if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; } return f[x][0]; }