LCA转换为RMQ

　2010-11-08 08:04:45　来源：WEB开发网　　　

核心提示：对有根树T进行DFS，将遍历到的结点按照顺序记下，LCA转换为RMQ，我们将得到一个长度为2N – 1的序列，称之为T的欧拉序列F每个结点都在欧拉序列中出现，我们记录结点u在欧拉序列中第一次出现的位置为we(u)例如下面图片中的一棵树:欧拉序列(QQ):1 2 5 2 6 2 1 3 1

对有根树T进行DFS，将遍历到的结点按照顺序记下，我们将得到一个长度为2N – 1的序列，称之为T的欧拉序列F

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

例如下面图片中的一棵树:

欧拉序列(QQ):1 2 5 2 6 2 1 3 1 4 1

深度序列(DP): 1 2 3 2 3 2 1 2 1 2 1

根据DFS的性质，对于两结点u、v，从pos(u)遍历到pos(v)的过程中经过LCA(u, v)有且仅有一次，且深度是深度序列B[we(u)…we(v)]中最小的

至此，LCA问题已经转换成了RMQ问题.

下面给出C++代码:

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
struct
{
      int x,y,n;
}e[200001];
int ff[200001];
int o,dp[200001],q[200001][20],f[200001][20];
bool v[200001];
int qq[200001],we[200001],time;
void add(int a,int b)
{
     e[++o].x=a;
     e[o].y=b;
     e[o].n=ff[a];
     ff[a]=o;
}
float log2(int n)
{
    return log10(n)/log10(2);
}
void dfs(int x,int deep)
{
     v[x]=true;
     qq[++time]=x;
     we[x]=time;
     dp[time]=deep;
     int t=ff[x];
     while  (e[t].y!=0)
     {
            dfs(e[t].y,deep+1);
            qq[++time]=x;
            dp[time]=deep;
            t=e[t].n;
     }
}
void find(int a,int b)
{
     int minn=(1<<30);
     int dk=(int)log2(b-a+1);
     if (f[a][dk]<f[b-(1<<dk)+1][dk]) minn=q[a][dk];
     else minn=q[b-(1<<dk)+1][dk];
     printf("%d\n",minn);
}

int main()
{
    freopen("turn.in","r",stdin);
    freopen("turn.out","w",stdout); 
    int n;scanf("%d",&n);
    o=0;
    time=0;
    for (int i=1;i<n;i++)
    {
        int a,b;scanf("%d%d",&a,&b);
        add(a,b);v[b]=true;
    }
    int biao;
    for (int i=1;i<=n;i++)
      if (v[i]==false) {biao=i;break;}
    dfs(biao,1);
    for (int i=1;i<=time;i++)
      f[i][0]=dp[i];
    for (int i=1;i<=time;i++)
      q[i][0]=qq[i]; 
    for (int j=1;j<=(int)log2(time);j++)
      for (int i=1;i<=time;i++)
      {
          if (i+(1<<j)-1>time) break;
          if (f[i][j-1]<f[i+(1<<(j-1))][j-1])
          {
                                             f[i][j]=f[i][j-1];
                                             q[i][j]=q[i][j-1];
          }else
          {
               f[i][j]=f[i+(1<<(j-1))][j-1];
               q[i][j]=q[i+(1<<(j-1))][j-1];
          }
      }  
        int a,b;
        scanf("%d%d",&a,&b);
        if (we[a]>we[b])
         find(we[b],we[a]);
         else find(we[a],we[b]);
    return 0;
}