第一种，倍增（O(nlogn)~O(logn)，在线）：

倍增的思想用在树上，即可以求出lca。

我们维护二维数组，f[i][j]，表示i号点的第2^j号祖先，显然2^0=1也就是f[i][0]就是他的父亲

我们需要用dfs维护一个深度数组（求lca需要用）

还需要倍增求出所有的f[i][j]，学过st的都应该知道，在这里f[i][j]=f[ f[i][j-1] ][j]

然后是我们的求lca了，很简单，首先要将这两个点u和v调到同一深度，这样以后操作都是同深度的。

怎么调深度呢？很简单，将他们的深度相减，我们设为dep，那么这个dep的就对应了深一点的那个点需要上升的高度，恩，应该马上能想到，直接用二进制表示深度然后一直爬上去就行了，这就是倍增的思想，log级别

同一深度时，我们要同时上升啦～我们继续用倍增思想，依次上升2^k的高度。什么时候上升呢？当然是f[u][k]!=f[v][k]的时候，因为这说明他们的祖先还不同，他们位于2棵子树，所以要上升。并且顺序要从大到小！否则求不到最小的祖先，很容易理解的。

代码很简单，12行

#include 
     
      #include 
      
       using namespace std;#define dbg(x) cout << #x << " = " << x << endl#define read(x) x=getint()#define rdm(u) for(int i=ihead[u]; i; i=e[i].next)const int N=10000, M=15;inline const int getint() { char c=getchar(); int k=1, ret=0; for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }struct ed { int to, next; } e[N<<1];int cnt, ihead[N], n, m, dep[N], fa[N][M];bool vis[N];inline void add(const int &u, const int &v) {	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;}void dfs(const int &u, const int &d) {	vis[u]=1; dep[u]=d;	rdm(u) if(!vis[e[i].to]) { dfs(e[i].to, d+1); fa[e[i].to][0]=u; }}inline void bz() { for(int j=1; j
       
        =0; --i) if((1<
        
         =0; --i) if(fa[u][i]!=fa[v][i]) u=fa[u][i], v=fa[v][i];	return fa[u][0];}int main() {	read(n); read(m);	for(int i=1; i

第二种，tarjan（O(n+并查集)~O(1) ，离线)：

速度略优于第一种。

tarjan求lca也很好理解的，我们假设现在的点为x

那么它子树作为一个已经被访问完的集合，并且在这些集合内的lca已经全部求出。

那么我们只要将这些子树和他子集合并就行了。

在这个集合求lca的方法很简单，用并查集即可。

代码也很短，也大概12行吧

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define dbg(x) cout << #x << " = " << x << endl#define read(x) x=getint()#define rdm(u) for(int i=ihead[u]; i; i=e[i].next)const int N=10005, M=10005;inline const int getint() { char c=getchar(); int k=1, ret=0; for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) ret=ret*10+c-'0'; return k*ret; }struct ed { int to, next; } e[N<<1];int cnt, ihead[N], n, m, lca[M], fa[N], p[N];bool vis[N];vector
        
         
           > q[N];inline void add(const int &u, const int &v) {	e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v;	e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u;}int ifind(const int &x) { return x==p[x]?x:p[x]=ifind(p[x]); }void tarjan(int u) {	p[u]=u;	rdm(u) if(e[i].to!=fa[u]) {		fa[e[i].to]=u; tarjan(e[i].to); p[e[i].to]=u;	}	vis[u]=1;	int t=q[u].size();	for(int i=0; i
          
            (u, i)); q[u].push_back(pair
           
             (v, i)); } tarjan(1); for(int i=1; i<=m; ++i) printf("%d\n", lca[i]); return 0;}

转载地址：http://egcba.baihongyu.com/

你可能感兴趣的文章

node.js爬虫爬取电影天堂，实现电视剧批量下载。