当前位置:首页 >> 学科竞赛 >>

LCA问题


LCA问题

LCA问题
? LCA:Lowest Common Ancestor基于有根树最近公共 祖先问题。 ? LCA(T,u,v):给定一棵有根树T和两个结点u和v, 找到 距离u和v的最近的共同祖先结点,称为LCA问题。

1.在线LCA的算法(又称为爬树法)

1.在线LCA的算法(又称为爬树

法)

1.在线LCA的算法(又称为爬树法)
? 如上图求LCA(a,b),当i=2时,p[a,2]=p[b,2](蓝色小圆);i 递减变为1,此时p[a,1]<>p[b,1],将a=p[a,1],b=p[b,1],完 成一次爬树;继续i递减变为0,此时p[a,0]<>p[b,0],再将 a=p[a,0],b=p[b,0],再向上完成一次爬树,循环结束;最终 p[a,0](或p[b,0])即是它们的最近公共祖先。

1.在线LCA的算法(又称为爬树法)
? 算法实现:首先我们构建一张表p[1..N,1..logN],这里P[i,j]指的是结点i 的第2^j个祖先。
void ST() //预处理 { int i,j; memset(p,-1,sizeof(p));//初始化 for(i=1;i<=n;i++)p[i][0]=prt[i];//指向父结点 for(j=1;j<=int(log(n)/log(2));j++) for(i=1;i<=n;i++) if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1]; } int LCA(int a,int b) //对于询问(a,b) { int k,i; if(d[a]<d[b])swap(a,b); //a的深度大于b k=int(log(d[a])/log(2)); for(i=k;i>=0;i--) //找到与b同层的结点 if(d[a]-(1<<i)>=d[b]) //即d(a)-2^i>=d(b) a=p[a][i]; //d(a)+2^i(上移到这层) if(a==b)return b; //a是b的子树 for(i=k;i>=0;i--) //计算LCA(a,b) if(p[a][i]!=-1&&p[a][i]!=p[b][i]){a=p[a][i];b=p[b][i];} return p[a][0]; }

2.LCA向RMQ的转化
? 对有根树T进行DFS,将遍历到的结点按照顺序记 下,我们将得到一个长度为2N-1的序列,称之为T 的欧拉序列F

? 每个结点都在欧拉序列中出现,我们记录结点u在 欧拉序列中第一次出现的位置为pos(u)

2.LCA向RMQ的转化
1 深度0

2

3

4

深度1

5

6

深度2

欧拉序列F:1 深度序列B:0

2 1

5 2

2 1

6 2

2 1

1 0

3 1

1 0

4 1

1 0

Pos (u):1

2

8

10

3

5

2.LCA向RMQ的转化
? 根据DFS的性质,对于两结点u、v,从pos(u)遍历到 pos(v)的过程中经过LCA(u, v)有且仅有一次,且深度 是深度序列B*pos(u)…pos(v)+中最小的 ? 即LCA(T, u, v) = RMQ(B, pos(u), pos(v)),并且问题规模 仍然是O(N)的

2.LCA向RMQ的转化
? 根据DFS的性质,对于两结点u、v,从pos(u)遍历到 pos(v)的过程中经过LCA(u, v)有且仅有一次,且深度 是深度序列B*pos(u)…pos(v)+中最小的 ? 这就证明了LCA问题可以转化成RMQ问题 ? LCA与RMQ问题可以互相转化,并且可以在O(N)的时 间内完成!

2.LCA向RMQ的转化
? 算法步骤: ? ①读入数据,建立有根树; ? ②DFS:从树T的根开始,进行深度优先遍历,求出 E[],L[],R[]的值; ? ③用RMQ来初始化; ? ④RMQ求解问题:当R[u]<=R[v]时, LCA[T,u,v]=RMQ(L,R[u],R[v]);否则LCA[T,u,v] = RMQ(L,R[v],R[u]),计算RMQ; ? 由于RMQ中使用的ST算法是在线算法,所以这个算 法也是在线算法。

void DFS(int x,int dep) //E[]为DFS序列,L[]为深度序列,R[]为首次访问 { vst[x]=1;//标记访问 cnt++;E[cnt]=x;L[cnt]=dep;R[x]=cnt; for(int i=h[x];i;i=w[i].next) { int y=w[i].to; if(!vst[y]) { DFS(y,dep+1); cnt++;E[cnt]=x;L[cnt]=dep; } } } void ST()//RMQ初始化深度序列L[] { int m=cnt,i,j; for(i=1;i<=m;i++)RMQ[i][0]=i; for(j=1;j<=int(log(m)/log(2));j++) for(i=1;i+(1<<j)-1<=m;i++) if(L[RMQ[i][j-1]]<L[RMQ[i+(1<<(j-1))][j-1]]) RMQ[i][j]=RMQ[i][j-1]; else RMQ[i][j]=RMQ[i+(1<<(j-1))][j-1]; }

void ASK() { int a,b,k,t,x,y; for(int i=1;i<=m;i++)//问题求解 { scanf("%d%d",&x,&y); if(R[x]>R[y]){a=R[y];b=R[x];}else{a=R[x];b=R[y];} k=int(log(b-a+1)/log(2)); if(L[RMQ[a][k]]<L[RMQ[b-(1<<k)+1][k]])t=RMQ[a][k]; else t=RMQ[b-(1<<k)+1][k]; printf("%d\n",E[t]); } } int main() { Init(); DFS(root,1); ST(); ASK(); }

3.离线LCA——Tarjan算法
? 解决LCA问题的Tarjan算法利用并查集在一次DFS (深度优先遍历)中完成所有询问。它是时间复 杂度为O(Na(N)+Q)的离线算法

3.离线LCA——Tarjan算法
? 考察树T中所有与结点u有关的询问(u, v)
p2 p1 v u v

v

对于子树u中的结点v,满足LCA(u, v) = v 对于子树p1而非子树u中的结点v,满足LCA(u, v) = p1 对于子树p2而非子树p1中的结点v,满足LCA(u, v) = p2

3.离线LCA——Tarjan算法
p2 p1 F(x) 算法DFS有根树T,定义从根节点到当前正在 遍历的结点u的路径为活跃路径P 对于每个已经遍历过的结点x,我们使用并查 集将其连接到P上距离其最近的结点F(x) F(x)

正在遍历

u F(x)

3.离线LCA——Tarjan算法
记录与u有关的询问集合为Q(u)
p2
p1

正在遍历

u

对于Q(u)中的任意一组询问LCA(u, v),如果 v已经遍历过,那么答案即为F(v) 我们只需要维护当前所有以遍历结点的F即可

3.离线LCA——Tarjan算法
记录与u有关的询问集合为Q(u)
p2

正在遍历
F

p1

u

1) 第一次遍历结点u时,有F(u) = u;
2)遍历完子树u后,子树u内任意结点w均 有F(w) = u;回溯回结点p1时,子树u 内任意结点w均有F(w) = p1,使用并查 集完成即可;

3.离线LCA——Tarjan算法
? 算法步骤: ? (1)读入数据,建立树结构,并记录下询问序列Q[],若有 (u,v)的询问,则(u,v)和(v,u)都要记录。 ? (2)Tarjan(x)算法 ①建立集合,自己为自己的父亲prt[x]=x; ②对当前节点x的每个儿子节点y进行深搜,并prt[y]=x; ③设置访问标记mark[x]=1,查找所有与x有关的回答,若 另一点已经访问了,则另一个点的祖先就是他们的最经公 共祖先。 ? (3)输出答案;

3.离线LCA——Tarjan算法
? 算法流程: Tarjan_DFS(u) 1) F(u) ? u; 2) For (u, v) ∈ Q(u) do Answer(u, v) ? F(v) 3) For v ∈ son(u) a) Tarjan_DFS(v); b) F(v) ? u; ?注:此处F采用并查集实现

3.离线LCA——Tarjan算法
void Tarjan(int x) { int i,y; vst[x]=1;prt[x]=x;//初始化 for(i=a0[x];i;i=a[i].next) //处理每个子树 { y=a[i].to; if(!vst[y]){Tarjan(y);prt[y]=x;} } mark[x]=1; //标记 for(i=q0[x];i;i=q[i].next)//回答与x有关的可以回答的询问 { y=q[i].to; if(mark[y])ans[q[i].num]=Get_Fa(y); } }

例题1:最近公共祖先1375

离线LCA——Tarjan算法
#include<iostream> #include<cstdio> using namespace std; const int maxn=200005; struct Edge{int to,next;}a[maxn*2]; struct Que{int to,next,num;}q[maxn*2]; int root,ans[maxn],a0[maxn]={0},q0[maxn]={0}; int vst[maxn]={0},prt[maxn],mark[maxn]={0},N,M,Na=0,Nq=0;

void Read() { int i,x,y; scanf("%d%d",&N,&M); for(i=1;i<=N-1;i++) { scanf("%d%d",&x,&y); Addedge(x,y);prt[y]=x;//Addedge(x,i); } for(i=1;i<=M;i++) {scanf("%d%d",&x,&y);Addque(x,y,i);Addque(y,x,i);} root=1; while(prt[root]!=0)root=prt[root]; } void Addedge(int x,int y)//添加边 ,建图 { Na++;a[Na].to=y;a[Na].next=a0[x];a0[x]=Na;} void Addque(int x,int y,int num)//用邻接表式添加询问 ,num表示第几次问的 { Nq++;q[Nq].to=y;q[Nq].next=q0[x];q0[x]=Nq;q[Nq].num=num;} int Get_Fa(int x) { if(prt[x]==x)return x; prt[x]=Get_Fa(prt[x]); return prt[x]; }

void Tarjan(int x) { int i,y; vst[x]=1;prt[x]=x; for(i=a0[x];i;i=a[i].next) { y=a[i].to; if(!vst[y]){Tarjan(y);prt[y]=x;} } mark[x]=1; for(i=q0[x];i;i=q[i].next)//回答与x有关的可以回答的询问 { y=q[i].to; if(mark[y])ans[q[i].num]=Get_Fa(y); } } int main() { Read(); Tarjan(root); for(int i=1;i<=M;i++)printf("%d\n",ans[i]); return 0; }

例题2:公共祖先问题2701
【问题描述】 给定一个包含n个节点的树,节点编号为1..n。其中,节点1 为树根。你的任务是给定这棵树的两个节点,快速计算出他们公 共祖先的个数。 【输入格式】 第一行一个整数n(1≤n≤50,000),表示树的节点个数。 接下来的n行,第i行表示节点i的信息。第i行第一个数字k, 表示节点i拥有孩子的个数,接着k个数字,表示这个节点所拥有 的孩子的编号。如果k=0,表示该节点是叶节点。注意,我们假定 节点是节点本身的祖先。 第n+2行是一个整数m(1≤m≤30,000),表示有m个查询。接下 去m行,每行两个数字x,y,表示该查询的两个节点的编号。 【输出格式】 对于每个查询,输出一行一个整数,表示这两个节点的公共 祖先的个数。

例题3:距离查询2664
? 给一棵树,要求你回答K个询问,即需要找到结点 X到结点Y的距离。 ? 【算法大意】DFS建树,每次建树记录下dis[i]表 示结点i到它的根节点的距离。对于任何一个询问 X与Y,如果我知道他们的最近公共祖先为结点C, 那么它们的距离就是dis[X]+dis[Y]-2*dis[C]。。


相关文章:
LCA问题
LCA问题_其它课程_高中教育_教育专区。LCA 问题 2007 年 08 月 15 日 星期三 下午 02:08 LCA 问题,即 Least Common Ancestors(最近公共祖先)的意思是:给定一...
LCA分析方法
生命周期指标总量的比例, 用于分析一个过程现场的直接 辨识问题出现的 贡献。 主要环节和原因 (可以是某过程 对总结果的影 该过程现场及其上游原料生产 响,也...
RMQ与LCA问题——ST算法
RMQ与LCA问题——ST算法_初中教育_教育专区。NOIP 信息学竞赛 高级数据结构一、ST 算法求解 RMQ 问题 RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。可...
LCA的发展与应用
LCA的发展与应用_环境科学/食品科学_工程科技_专业资料。LCA的发展与应用 LCA的发展与应用一、LCA的发展 LCA的发展 1.1 LCA的发展过程及概念 环境协调性评价起始...
参考诊断标准及注意事项
颈动脉超声检查时应注意的问题 1、角度问题: 线阵探头不要调整角度 凸阵探头...ICA 狭窄诊断参考标准 lCA 狭窄诊断参考标准 PSV lCA EDV lCA PSV lCA / PSV...
1什么是环境问题
环境问题是指由于人类活动作用于周围环境所引起的环境质量变化, 以及这种变 化对...LCA 已经纳入 ISO14000 环境管理系列标准而成为国际上环 境管理和产品设计的一个...
材料LCA计算模型与评价方法
材料LCA计算模型与评价方法_电力/水利_工程科技_专业资料。材料 LCA 计算模型与...国国情的特征化模型, 是材料环境协调性评价研究进行本土化所 面临的重要问题之...
LCA
2页 1财富值 RMQ LCA问题与ST(Sparse T... 5页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
LCA理论研究综述
如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 LCA理论研究综述 隐藏>> LCA 理 论 研 究 综 述 分享到: X ...
环境材料学
框架: 目标和范围定义:界定某一过程、产品或事件对环境影响的大小(LCA 方法应用...就产 生了输入输出数据如何在多个产品系统间分配的问题 (从系统中的物理、 ...
更多相关标签:
lca | lca算法 | tarjan算法 | 欧拉路 | 李晨被曝卖问题车 | 不成问题的问题 | 督察组晒4省问题 | 一直播常见问题有哪些 |