树上问题中，有个相当著名而又较为困难的问题，即最近公共祖先问题（Least Common Ancestors），又简称LCA问题。我们先了解一下何为LCA吧。

LCA，即已知一棵有根树，求问两个节点的最近的公共祖先是哪个节点。

从最朴素的算法去思考，我们只要找到这两个节点的深度，先从最深的节点向上搜索，找到与另一个节点深度相同的节点，而后这两个节点同时向上搜索直到这两个节点相遇，该节点即为所求。由树的性质我们知道，每个节点在每层只有一个祖先，故而此算法可行。然而，我们发现如果这棵树退化为近乎一条链，那么其时间复杂度会高达O(n^2)，这显然是无法接受的。这时我们可以用上倍增法，从而将时间复杂度降至O(nlogn)。

那么何为倍增算法呢？举个例子以帮助理解吧。有一个人，想要离家出走，但又离家太远的地方是危险区，他想要去离家最远而又不算危险区的那个临界点，可是这个人又不知道离家多远才到危险区，不过不会超过2^100米远。但是他家有电脑，他可以查看离家一个已知距离的点是否危险。朴素算法就是先看离家1米再看离家2米，这显然太耗时了。于是他先查看2^100米远的点，发现在危险区，而后查看2^99米远的点，发现不在。由于他知道，2^100==2^99+2^99。于是他在2^99米远的点再往后查看2^98米远的点，如果在危险区则查看2^98米······以此类推，最后他只要查看在当时位置向前移动2^0米，即1米的距离是否到达危险区，若是，则当前位置为所求，否则为前进1米的位置。于是，利用这个算法，本来要找2^100次，现在只要100次我们就能找到，时间复杂度由O(n)降至O(logn)。

当然，我们也可以用二分答案法以O(logn)找到正解，这儿就不多赘述了。

接下去我们来考虑如何用倍增法解决LCA问题。我们可以让深度大的那个节点向上以该逻辑进行大跳，直到与另一个节点深度相同，而后两节点共同向上大跳，找到最近的相遇点，该点即为所求。而通常题目会求多组节点的LCA，这时我们往往会先将每一个节点的祖先利用倍增求出，其求法为fa[x][i]=fa[fa[x][i-1]][i-1]，其中fa[x][i]指从x节点向上走2^i步的节点，它就是从x节点向上走2^i-1步之后向上走2^i-1步所得的节点。而后再求多组的LCA。

接下来我们以一道例题来搞清楚具体操作如何实现。

 

洛谷p3379

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 N,M,S分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N-1 行每行包含两个正整数 x, y表示 x结点和 y结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 M行每行包含两个正整数 a, b表示询问 a结点和 b结点的最近公共祖先。

输出格式

输出包含 M行，每行包含一个正整数，依次为每一个询问的结果。

说明/提示

对于 30% 的数据，N≤10，M≤10。

对于 70% 的数据，N≤10000，M≤10000。

对于 100% 的数据，N≤500000，M≤500000。

 

首先我利用vector建立了一个无向图（注意不能是有向图）。

 

for(int i=1;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

 

而后利用倍增法深搜求出每个点的祖先。

void dfs(int x,int y){//y为x的父亲
    dep[x]=dep[y]+1;//x的深度为y+1
    fa[x][0]=y;//y为x的父亲，即x向上走2^0步
    for(int i=1;pow(2,i)<=dep[x];i++){//注意不能走得超过根节点
        fa[x][i]=fa[fa[x][i-1]][i-1];//x向上走2^i步为x向上走2^i-1步之后向上走2^i-1步
    }
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=y)dfs(v[x][i],x);//向下深搜
    }
}

求出LCA。

int log2(int x){//建立了一个以2为底的对数函数叫log2（）。
    return (int)(log(x)/log(2));
}
int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);//保持x比y深，便于计算
    while(dep[x]>dep[y])x=fa[x][log2(dep[x]-dep[y])];//利用倍增法求出x的与y同深的节点。因为log2向下取整，所以可能一次消不掉故而用while。
    if(x==y)return x;//y就是x的祖先，直接返回x
    for(int i=log2(dep[x]);i>=0;i--){//x与y一起向上走2^i步
        if(fa[x][i]!=fa[y][i]){//注意相同可能是走过了，也可能是走到了，都按走过头了处理，因为最后差距一定只有2^0步
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];//返回父亲节点
}

完整AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
vector<int> v[N];
int log2(int x){
    return (int)(log(x)/log(2));
}
int fa[N][40];
int dep[N];
void dfs(int x,int y){
    dep[x]=dep[y]+1;
    fa[x][0]=y;
    for(int i=1;pow(2,i)<=dep[x];i++){
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int i=0;i<v[x].size();i++){
        if(v[x][i]!=y)dfs(v[x][i],x);
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])x=fa[x][log2(dep[x]-dep[y])];
    if(x==y)return x;
    for(int i=log2(dep[x]);i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
int main(){
    int n,m,s;
    scanf("%d %d %d",&n,&m,&s);
    memset(fa,0,sizeof(fa));
    memset(dep,0,sizeof(dep));
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(s,0);//从根遍历
    while(m--){
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
    return 0;
}

（马上又要比赛了，饭还没吃，溜了