最近公共祖先（LCA）

概念

首先，我们要了解LCA的概念。
什么是LCA？？？？？？
让我们看一副图

然后,我们要查找\(2\)，\(4\)的最近公共祖先。
显然我们找到的是\(4\)。
那么，我们就可以知道，最近公共祖先就是\(\color{#FF0000}{两个节点在这棵树上深度最大的公共的祖先节点}\)
换句话说，也就是\(\color{#FF0000}{两个点在这棵树上距离最近的公共祖先节点}\)

做法

一般来说，我们会想到\(\color{#FF0000}{暴力}\)：对于每个询问，遍历所有的点，时间复杂度为O(n*q)，很明显，\(\color{#FF0000}{n和q一般不会很小}\)。
\(But\) 在洛谷中，我们可以得70分。
在这里，我来分享一下。

暴力

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+5;
vector <int> e[maxn];//vector，相信没有人不会
int d[maxn],f[maxn];
/*
d[i]指i节点的深度
f[i]指i节点的父亲节点
*/
void dfs(int x,int fa){
    d[x]=d[fa]+1;//求深度
    f[x]=fa;
    for(int i=0;i<e[x].size();i++){
        int y=e[x][i];
        if(y!=fa)dfs(y,x);//由于存边时存的时无向边，所以要防止搜回父亲节点，但也可以用一个vis[]来标记查过的节点
    }
}
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);//存边
    }
    dfs(s,0);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(d[x]<d[y]){int tmp=x;x=y;y=tmp;}//将顺序调成x<y，可以用swap()
        while(d[x]>d[y]){x=f[x];}
        while(x!=y){
            x=f[x];y=f[y];
        }//如果x!=y，就搜它们的父亲节点（很慢很慢）
        printf("%d\n",x);
    }
    return 0;
}

接下来，我们来拿满分（AC）

倍增（这一部分转自\(jarjingx\)的\(csdn\)）

序言

我认为吧，所有能够优化复杂度的算法都是神奇的，所有能够化繁琐为形象的文字都是伟大的。一直觉得倍增算法是个很神奇的东西，所以决定写点东西纪念一下它。但是作为一个非常不称职的OIER，我非常讨厌在看别人的算法解析时整版的i，j，k等我看到鼠标就惯性移到右上角的符号语言，所以我想用最形象的方式来纪念它。

一

从前，有一只可爱得不得了的小白兔，它想从A地去往遥远的B地。

2B小白兔：
向右边跳一步，左边跳一步，再向右边跳很多步，再……（对不起，这个太脑残了）
普通小白兔：
向右边跳一步，再跳一步，再跳一步……再跳一步，哇，到了！好开心！
超级小白兔：
向右边跳一大步，一步跳到B，然后默默回头，鄙视一下那只一步一步跳的小白兔。

我相信作为一个正常人，是不会考虑到2B小白兔的这种做法的，因为它太脑残了。
同时我也相信，作为一个正常人，也不会考虑到超级小白兔的这种做法的，因为……
“我擦！你什么时候说可以这样跳了！（愤怒）”
“我什么时候说不可以了！（卖萌）”
但是你不得不承认，超级小白兔还是有两把刷子的，因为它真的是太厉害了，厉害得你想都没有想到。

二

从前，有一只可爱得不得了的小白兔，它想从A地去往遥远的B、C、D、E、F这几个让它魂牵梦萦的地方。（不要问我从哪里来，我的梦想在远方）

2B小白兔：
（对不起，我的生命有限，我不想再提到它了）
普通小白兔：
一步又一步，生命不息，跳跃不止。
超级小白兔：
一步到B，再一步到C，再一步到D，再一步到E，再一步到F，完工。

你不用解释，我深知你就想当那只超级小白兔，哼，你肯定是那样跳的。（神马？不是？兄弟你的智商我救不了了……）

    是的，不这样跳的人对不起社会啊，浪费时间就是浪费青春，浪费青春就是犯罪。

    好的，既然你是这样跳的，那你能告诉我你是怎么知道从A只要跳2个格子就会刚好到B的？难道你在空中使用了GPRS全球卫星定位系统？你少来好么！主页君现在都没用过这种东西，你一只白白嫩嫩下酒菜的小兔子还用这个？笑死我吗？哈哈，你一定是出发前就偷偷学普通兔子一步一步跳过一遍，然后拿个本子做小抄，记录好从每个格子跳任意步会到达的地方，然后赶在天亮之前回来，风光的按照踩点计划大步的跳，让我们觉得你很厉害的样子，我没说错吧？不过看在你有这个诚心的份上，还是为你的聪明鼓掌吧。

三

从前，有一只可爱得不得了的小白兔，它想从A地去往遥远的1（此处省略很多0）个地方，因为它真的是太没事情做了。

普通小白兔：
从离开家门的那天起，我就没有想过要放弃一步一步地跳往终点。（嗯，加油）
超级小白兔：
轻轻松松，绝不多走一步。（哼哼）

你想知道最后的结果吗？呵呵，好像还没有出结果……

写给普通小白兔的话：
亲爱的小白兔，我知道你勇毅，你质朴，但是，苦海无涯，回头是岸。

写给超级小白兔的话：
我不知道你的小抄本是否还够用，我不知道你摸着黑就出门是为了什么，你不觉得你的行踪早就已经暴露了吗？你以为你很聪明吗？不，你错了，你就一下酒菜，永远都是，因为你不知道倍增算法，这是你失败的根源，再见，我心中永远不会逝去的蠢兔子。

——————————————————分割线—————————————————————————

最近公共祖先（LCA）

原文：https://www.cnblogs.com/xzj213/p/11005649.html