LCA问题
给定一棵有根树T,对于任意两个节点u,v，求出LCA(T,u,v)
LCA的tarjan算法 （离线算法）
//初始所有节点color为WHITE
void LCA(u)
{
MAKE_SET(u);
ancester[FIND_SET(u)]=u;
for(u的每个儿子v)
{
LCA(v);
UNION(u,v);
ancester[FIND_SET(u)]=u;
}
color[u]=BLACK
for(Q(u)中的所有元素)
{
if(color[v]==BLACK)
printf("LCA(%d,%d)=%d\n",u,v,ancester[FIND_SET(v)]);
}
}
MAKE_SET(u)表示建立一个只有u的集合，且u为集合的代表元
FIND_SET(u)表示找出集合的代表元
UNION(u,v) 表示合并u,v所在的集合
RMQ问题
给定一个长度为n的数组n，回答询问RMQ(A,i,j)，即A[i..j]中元素最小的数的下标
将LCA问题转化为RMQ问题
1.DFS遍历树，记录遍历到的节点E[1..2n-1],
并用R[i]表示E数组中第一个值为i的元素的下标
2.对于任意 R[u]<R[v] ,dfs中第一次访问u到第一次访问v的路径是E[R[u]..R[v]]
并且其中深度最小的节点一定是u,v的LCA
3.令数组L[i]表示节点E[i]的深度，那么当R[u]<R[v]时，LCA(T,u,v)=RMQ(L,R[u],R[v]);
转换后的RMQ问题比较特殊，相邻两个元素的相差1或-1，这样的问题成为+_1-RMQ
一般RMQ的Spare Table(ST) 算法
d[i,j]表示从i开始长度为2^j的区间的RMQ，
则有递推公式 d[i,j]=min(d[i][j-1],d[i+2^(j-1),j-1]),即用两个相邻的长度为2^(j-1)
的区间来分形长度为2^j的区间 预处理时间复杂度为O(nlogn)
询问时 取k=log2(j-i+1)令A为从i开始的长度为2^k的块的RMQ
令B为到j结束的长度为2^k的块的RMQ
则RMQ(i,j)=min(A,B),
即 k=log2(j-i+1),RMQ[i,j]=min(d[i,k],d[j-2^k+1,k])
+_1-RMQ的O(n)-O(1)算法
………………………………
未完待续…………
////////
写了个lca的代码
不知道对不对
#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxn 505
#define black 1
#define white 0
int father[maxn],ancester[maxn];
int color[maxn];
struct node
{
int v,next;
} edge[maxn*maxn];
int p[maxn];
int n,e,m;
int root;
void add(int u,int v)
{
edge[e].v=v;
edge[e].next=p[u];
p[u]=e++;
}
int find(int u)
{
if (u==father[u]) return u;
else
{
father[u]=find(father[u]);
}//路径压缩
return father[u];
}
void union1(int u,int v)
{
int tmp,tmp1;
tmp=find(u);
tmp1=find(v);
father[tmp1]=tmp;
}
void lca(int u)
{
int i,v,v1;
father[u]=u;
ancester[find(u)]=u;
for(i=p[u]; i!=-1; i=edge[i].next)
{
v=edge[i].v;
lca(v);
union1(u,v);
ancester[find(u)]=u;
}
/*for(i=p1[u]; i!=-1; i=edge1[i].next)
{
v1=edge1[i].v;
if (color[v1]==black)
printf("LCA(%d,%d)=%d\n",u,v1,ancester[find(v)]);
}*/
color[u]=black;
for(i=1;i<=n;i++)
if(i!=u)
{
if (color[i]==black)
{
printf("LCA(%d,%d)=%d\n",u,i,ancester[find(i)]);
}
}
}
int main()
{
int a,b,i;
scanf("%d%d",&n,&m);
scanf("%d",&root);
memset(p,-1,sizeof(p));
e=0;
for(i=1; i<=m; i++)
{
scanf("%d%d",&a,&b);
add(a,b);
}
for(i=1; i<=n; i++) father[i]=i;
memset(color,white,sizeof(color));
lca(1);
return 0;
}