最近公共祖先 LCA 倍增法

【简介】

      解决LCA问题的倍增法是一种基于倍增思想的在线算法。

【原理】

     原理和同样是使用倍增思想的RMQ-ST 算法类似,比较简单,想清楚后很容易实现。

     对于每个节点u , ancestors[u][k] 表示 u 的第2k个祖先是谁。很容易就想到递推式: ancestors[j][i] = ancestors[ancestors[j][i - 1]][i - 1];  根据二进制原理,理论上 u 的所有祖先都可以根据ancestors数组多次跳转得到,这样就间接地记录了每个节点的祖先信息。
     查询LCA(u,v)的时候:
         (一)u和v所在的树的层数如果一样,令u‘=u。否则需要平衡操作(假设u更深),先找到u的一个祖先u‘, 使得u‘的层数和v一样,此时LCA(u,v)=LCA(u‘,v) 。证明很简单:如果LCA(u,v)=v , 那么u‘一定等于v ;如果LCA(u,v)=k ,k!=v ,那么k 的深度一定小于 v , u、u‘、v 一定在k的子树中;综上所述,LCA(u,v)=LCA(u‘,v)一定成立。

         (二)此时u‘ 和 v 的祖先序列中一开始的部分一定有所重叠,重叠部分的最后一个元素(也就是深度最深,与u‘、v最近的元素)就是所求的LCA(u,v)。这里ancestors数组就可以派上用场了。找到第一个不重叠的节点k,LCA(u,v)=ancestors[k][0] 。 找k的过程利用二进制贪心思想,先尽可能跳到最上层的祖先,如果两祖先相等,说明完全可以跳小点,跳的距离除2,这样一步步跳下去一定可以找到k。

【hdu 2586】

      需要注意的是超界的处理。

最近公共祖先 LCA 倍增法
  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <vector>
  5 #include <cmath>
  6 #include <iostream>
  7 using namespace std;
  8 int n,m;
  9 struct edge
 10 {
 11     int d,v,next;
 12     edge(){}
 13     edge(int _d,int _v,int _next)
 14     {
 15         d=_d;v=_v;next=_next;
 16     }
 17 }data[80003];
 18 int map[40003];
 19 int pool;
 20 void addedge(int s,int e,int v)
 21 {
 22     int t=map[s];
 23     data[pool++]=edge(e,v,t);
 24     map[s]=pool-1;
 25 }
 26 int ANCLOG;
 27 int depth[40003];
 28 int ifv[40003];
 29 int dis[40003];
 30 int anc[40003][17];
 31 void dfs(int cur,int dep)
 32 {
 33     ifv[cur]=1;
 34     depth[cur]=dep;
 35     int p=map[cur];
 36     while (p!=-1)
 37     {
 38        if (!ifv[data[p].d])
 39        {
 40            dis[data[p].d]=dis[cur]+data[p].v;
 41            anc[data[p].d][0]=cur;
 42            dfs(data[p].d,dep+1);
 43        }
 44         p=data[p].next;
 45     }
 46 }
 47 void initLCA()
 48 {
 49     for (int k=1;k<ANCLOG;++k)
 50        for (int i=0;i<n;++i)
 51     {
 52         if (anc[i][k-1]==-1) continue;
 53         anc[i][k]=anc[anc[i][k-1]][k-1];
 54     }
 55 }
 56 int getLCA(int u,int v)
 57 {
 58     if (depth[u]<depth[v]) swap(u,v);
 59     for (int k=ANCLOG;k>=0;--k)
 60     {
 61         if (anc[u][k]==-1) continue;
 62         if (depth[anc[u][k]]>=depth[v])
 63         {
 64             u=anc[u][k];
 65             if (depth[u]==depth[v]) break;
 66         }
 67     }
 68     if (u==v) return u;
 69     for (int k=ANCLOG;k>=0;--k)
 70     {
 71          if (anc[u][k]==-1) continue;
 72          if (anc[u][k]!=anc[v][k])
 73          {
 74              u=anc[u][k];
 75              v=anc[v][k];
 76          }
 77     }
 78     return anc[u][0];
 79 }
 80 int main()
 81 {
 82     int T;
 83     scanf("%d",&T);
 84     while (T--)
 85     {
 86         pool=0;
 87         memset(anc,-1,sizeof anc);
 88         memset(map,-1,sizeof map);
 89         memset(ifv,0,sizeof ifv);
 90         scanf("%d%d",&n,&m);
 91         ANCLOG=(int)(log(n)/log(2.0));
 92         int s,e,v;
 93         for (int i=0;i<n-1;++i)
 94         {
 95             scanf("%d%d%d",&s,&e,&v);
 96             addedge(s-1,e-1,v);
 97             addedge(e-1,s-1,v);
 98         }
 99         dis[0]=0;
100         dfs(0,0);
101         initLCA();
102         for (int i=0;i<m;++i)
103         {
104             int u,v;
105             scanf("%d%d",&u,&v);
106             --u;--v;
107             int k=getLCA(u,v);
108             k=dis[u]+dis[v]-2*dis[k];
109             printf("%d\n",k);
110         }
111     }
112 }
View Code

最近公共祖先 LCA 倍增法

上一篇:前后端开发分离为什么提高效率?【2014-01-24】


下一篇:Java多线程系列--“JUC锁”06之 Condition条件