原来学习最小生成树的时候写了道题，发现得用最近公共祖先迫于无奈便学了LCA（不过确实很有用）
LCA主要基于一种倍增的思想，和st表很像，通过预处理数据来花费空间换取时间。
要想学习怎么求LCA首先要学习LCA是什么。
在一颗数中，比如说图中的4和5，那么他们的最近公共祖先便是2。
如果是2和3他们的最近公共祖先便是1，而2和4的最近公共祖先是2本身，所以最近公共祖先也可以是自己。
那么要如何来求呢。最朴素的做法是用dfs进行搜索查找，但这样的时间复杂度太高了。
于是就出现了这种基于倍增的LCA。
这里盗用一张洛谷的图，上面那图太小了
------------恢复内容开始------------
原来学习最小生成树的时候写了道题，发现得用最近公共祖先迫于无奈便学了LCA（不过确实很有用）
LCA主要基于一种倍增的思想，和st表很像，通过预处理数据来花费空间换取时间。
要想学习怎么求LCA首先要学习LCA是什么。
在一颗数中，比如说图中的4和5，那么他们的最近公共祖先便是2。
如果是2和3他们的最近公共祖先便是1，而2和4的最近公共祖先是2本身，所以最近公共祖先也可以是自己。
那么要如何来求呢。最朴素的做法是用dfs进行搜索查找，但这样的时间复杂度太高了。
于是就出现了这种基于倍增的LCA。
这里盗用一张洛谷的图，上面那图太小了
比如说我们想求17和8的公共祖先，我们便要考虑将17和8给弄到同一层（即树的深度，第一层的深度是1）
17比8的深度要深，所以得先把17往上面爬。
如果一层一层的爬，那效率便太低了，所以我们便考虑一此直接爬2^n层。
比如这里17爬到10，我们直接爬2^1层，便不用爬两次了。
爬到相同的层数之后，我们还要继续爬，不过这时是两边一起爬相同的层数，也是一次爬2^n层，一直到爬到相同的节点便ok了，这时的这个节点便是我们要找的最近公共祖先。
讲了那么多现在最重要的便是如何实现了。
话不多说先上代码再讲解（这里是数据的预处理阶段采用dfs）
void dfs(int here,int fa) {//here表示目前所在的节点，fa表示当前节点的父节点
vis[here] = 1;//用一个数组储存是否到过这个节点其实没什么用
depth[here] = depth[fa] + 1; f[here][0] = fa;//depth代表节点深度的数组
for (int i = 1; i <= lg[depth[here]]; i++) //lg数组代表着对里面的数取log2，也可以用log2（）函数代替，不过会慢？
f[here][i] = f[f[here][i - 1]][i - 1];//这里是一个dp，也是倍增的核心，主要原理是2^i=2^(i-1)*2^(i-1)
for (int i = head[here]; i; i = a[i].nex)//这里是链式前向星存边没啥好说的
if(!vis[a[i].to])
dfs(a[i].to, here);
}
这步预处理是算法的核心，而这步的核心便是对二维数组f[i][j]的操作
这个数组中储存的数代表着i这个节点往上跳2^j步所到的节点。
预处理完了便是查找了。
int LCA(int x,int y) {
if (depth[x] < depth[y])swap(x, y);//由于我们要找个深度最深的先往上跳所以无论输入的xy哪个最深，我们让x在树中深度最深，然后对x进行操作
while (depth[x] > depth[y]) x = f[x][lg[depth[x] - depth[y]]];//用这个循环来让x和y达到同一层
if (x == y) return x;//特判一下如果如果xy此时节点相同的化，直接return，节约时间。
for (int i = lg[depth[x]]; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}//让x和y一同往上跳，如过跳到下一层他们就相同就不跳了
return f[x][0];因为下一层才相同，所以return x往上跳2^0层
}
这样LCA大概就讲完了，最后附上全部代码
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdio.h>
#include<vector>
#define maxx 1000005
using namespace std;
int head[maxx], now = 0, n, m, lg[maxx], f[maxx][32], depth[maxx], vis[maxx], p;
struct edge {
int nex, to;
}a[maxx*2];
void add_edge(int at, int to) {
a[++now].nex = head[at];
a[now].to = to;
head[at] = now;
}
void swap(int& x, int& y) {
int temp = x; x = y; y = temp;
}
void dfs(int here,int fa) {
vis[here] = 1;
depth[here] = depth[fa] + 1; f[here][0] = fa;
for (int i = 1; i <= lg[depth[here]]; i++) {
f[here][i] = f[f[here][i - 1]][i - 1];
}
for (int i = head[here]; i; i = a[i].nex)
if(!vis[a[i].to])
dfs(a[i].to, here);
}
int LCA(int x,int y) {
if (depth[x] < depth[y])swap(x, y);
while (depth[x] > depth[y]) x = f[x][lg[depth[x] - depth[y]]];
if (x == y) return x;
for (int i = lg[depth[x]]; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
int main() {
cin >> n >> m >> p;
for (int i = 1; i <= n-1; i++) {
int at, to, l; cin >> at >> to;
add_edge(at, to);
add_edge(to, at);
}
lg[0] = -1;
for (int i = 1; i <= n; i++) {
lg[i] = lg[i >> 1] + 1;
}
dfs(p, 0);
for (int i = 1; i <= m; i++) {
int x, y; cin >> x >> y;
cout << LCA(x, y) << endl;
}
return 0;
}
代码比较丑，多多包含