最小公共祖先(_LCA_)问题解读.ppt

最小公共祖先( LCA )问题 poj1330,1986,1470--fuyuchang(cc)internet 大纲 定义 将 LCA 问题转化为 RMQ 问题 RMQ 的一般解法 ±1 RMQ 问题的快速解法 RMQ 的快速解法 LCA – 最小公共祖先 在树T中，结点u和v的最小公共祖先是它们共有的、离根结点最远的那个祖先结点。 LCAT(u,v) u v RMQ – 区间最小询问 询问 RMQA(i,j) 返回的是数组A[i..j]中最小元素的下标。 RMQA(i,j) 0 16 34 13 7 19 10 12 1 2 RMQA(3,7) = 4 A[0] A[2] A[1] A[9] A[3] A[4] A[5] A[6] A[7] A[8] 时间复杂度标记 预处理时间 单个询问处理时间 LCA – 一般的算法 对任意一对结点，分别找出它们到树根的路径，然后在这两条路经中找第一个公共的结点。 复杂度 = LCA普通算法的图 将 LCA 转化为 RMQ 如果有一个复杂度为 的 RMQ解法，那么就存在一个复杂度为 的LCA解法。 变形 – 根据树T构造3个数组 1. E[1..2n-1]：存放从树根开始的Euler遍历所经过的结点编号。 2. L[1..2n-1]：L[i]存放E[i]结点在树T中的深度。 3. P[1..n]： R[i]表示结点i在数组E中第一次出现的下标。 8 例 0 1 2 3 6 9 5 4 7 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Eu: 0 1 2 1 3 1 0 4 0 5 6 5 7 8 7 5 9 5 0 id: 0 1 2 1 2 1 0 1 0 1 2 1 2 3 2 1 2 1 0 P: 0 1 2 4 7 9 10 12 13 16 计算 LCAT(u,v) Euler 遍历过程中，夹在u和v第一次被访问中间的结点是E[R[u],…,R[v]]。 其中深度最小的结点的下标是 RMQL(R[u],R[v])。 LCAT(u,v)的结果就是 E[RMQL(R[u],R[v])]。 例 – LCAT(6,9) 0 1 2 3 6 9 5 8 4 7 E: 0 1 2 1 3 1 0 4 0 5 6 5 7 8 7 5 9 5 0 L: 0 1 2 1 2 1 0 1 0 1 2 1 2 3 2 1 2 1 0 P: 0 1 2 4 7 9 10 12 13 16 R[6] R[9] E[10,…,16] RMQL(10,16) = 11 LCAT(6,9) = E[11]=5 复杂度分析 预处理 数组构造：O(n)。 根据假设，对数组 L 进行预处理：f(2n-1)。 询问处理 三个数组的访问： O(1)。 根据假设，对数组 L 进行RMQ询问处理：g(2n-1)。 总共： RMQ-LCA在线算法部分代码 bool visit[MAXNODE]; int oula[2*MAXNODE],dist[MAXNODE],pos[MAXNODE],minrmq[18][2*MAXNODE],id[MAXNODE]; int n,m; void add(int u, int v, int w) { edge[e].to = v; edge[e].w = w; edge[e].next = head[u]; head[u] = e++; } void init(){ rst(head,-1); rst(visit,false); tmpdfn=0; index=0; e=0; } void dfs(int u){ visit[u]=true; int len; int oulanum=++tmpdfn; oula[++index]=oulanum; pos[u]=index; id[oulanum]=u; for(int i=head[u];i!=-1;i=edge[i].ne