概念

公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点

举个例子吧，如下图所示4和5的最近公共祖先是２，５和３的最近公共祖先是１，２和１的最近公共祖先是１。

算法

常用的求LCA的算法有：Tarjan/DFS+ST/倍增

其中 ：ST和倍增都是在线的；Taijian是离线的

这里介绍离线的Tarjian算法

基本思想：

1.任选一个点为根节点，从根节点开始

2.遍历该点u所有子节点v，并标记这些子节点v已被访问过

3.若是v还有子节点，返回2，否则下一步

4.合并v到u上

5.寻找与当前点u有询问关系的点v

6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。

代码

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 5200000

struct data {

    int next;

    int to;

    int lca;             //存每一次询问的答案

};

data edge[N];

data qedge[N];

int n,m,p,x,y;

int tot_edge,tot_qedge,head[N],qhead[N];

int fa[N];

int visit[N];

template<typename T>inline void read(T&x){

    x=0;T y=1;char c;

    while(c=getchar(),c<48||57<c) if(c=='-')y=-1;x=c^48;

    while(c=getchar(),47<c&&c<58) x=(x<<1)+(x<<3)+(c^48);x*=y;

}

void add_edge(int u,int v) {

    edge[++tot_edge].next=head[u];

    edge[tot_edge].to=v;

    head[u]=tot_edge;

}

void add_qedge(int u,int v) {       //建立需要查询LCA的两节点的链表

    qedge[++tot_qedge].next=qhead[u];

    qedge[tot_qedge].to=v;

    qhead[u]=tot_qedge;

}

int find(int z) {

    return fa[z]==z?z:find(fa[z]);

    /*if(fa[z]!=z)

        fa[z]=find(fa[z]);

    return fa[z];*/

}

int dfs(int x) {                  //把整棵树的一部分看作以节点x为根节点的小树

    fa[x]=x;                      //由于节点x被看作是根节点，所以把x的fa设为它自己

    visit[x]=1;                   //标记为已被搜索过

    for(register int k=head[x]; k; k=edge[k].next)         //遍历所有与x相连的节点

        if(!visit[edge[k].to]) {                  //若未被搜索

            dfs(edge[k].to);

            fa[edge[k].to]=x;                     //把x的孩子节点的fa重新设为x

        }

    for(register int k=qhead[x]; k; k=qedge[k].next) //搜索包含节点x的所有询问

        if(visit[qedge[k].to]) { //如果另一节点已被搜索过

            qedge[k].lca=find(qedge[k].to);//把另一节点的祖先设为这两个节点的最近公共祖先

            if(k%2)//由于将每一组查询变为两组，所以2n-1和2n的结果是一样的

                qedge[k+1].lca=qedge[k].lca;

            else

                qedge[k-1].lca=qedge[k].lca;

        }

}

int main() {

    read(n);

    read(m);

    read(p);                      //n:边数,m:查询次数,p:根的编号

    for(register int i=1; i<n; ++i) {

        read(x);

        read(y);      //每条边

        add_edge(x,y);

        add_edge(y,x);

    }

    for(register int i=1; i<=m; ++i) {

        read(x);

        read(y);      //输入每次查询，考虑(u,v)时若查找到u但v未被查找，所以将(u,v)(v,u)全部记录

        add_qedge(x,y);

        add_qedge(y,x);

    }

    dfs(p);                         //进入以p为根节点的树的深搜

    for(register int i=1; i<=m; ++i)

        printf("%d\n",qedge[i*2].lca);           //两者结果一样，只输出一组即可

    return 0;

}

入门题目

CODEVS 2370 小机房的树

CODEVS 1036 商务旅行

METO CODE 223 拉力赛

ZOJ 3195 Design the city