最近公共祖先 LCA 洛谷 P3379
今天 xiao 习了一下 LCA 过程十分曲折。。。
（检查的时候主函数没有调用 dfs，调试了好几遍才发现。。。
首先，我们先来看一看定义：最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
它有三种做法：
- 暴力
- 倍增
- 树链剖分
遗憾的是我就会前两种；
第一种枚举
我们有了这么一棵树，和其中的两个节点；那么我们只需要一个一个求出它们的祖先，一步步向上跳就可以找到交点，找到第一个交点就是最近公共祖先
显而易见，这是最为朴素的正解；
但不是最优解；
仔细一想就知道他可顶复杂度超高（给两个叶子结点最后回到根上）
明显过不去
那么就要想方设法优化
第二种方法 倍增
倍增求 LCA 是最经典的方法了（不要问我谁提出来的问就是不知道）
上面朴素做法是一步一步向上跳，那么我们就可以很多步很多步向上跳，就可以优化；
而倍增就是优化的方法之一，以 logn 的时间复杂度来向上查询
只需要预处理出一个数组 f[u][i]u 是节点，i 是指 u 向上 2^i 个节点处（第 2^i 个祖先
那么我们就可以一步一步向上跳
第三种方法 树链剖分
我不会。。。……以后再写
上代码
#include<bits/stdc++.h>
using namespace std;
#define maxn 1000010
struct mm
{
/* data */
int next,v;
}cun[maxn];
int head[maxn],d[maxn],f[maxn][22],tot;
void add(int x,int y)
{
cun[++tot].next=head[x];head[x]=tot;cun[tot].v=y;//结构体存链表
}
void dfs(int u,int fa)
{
d[u]=d[fa]+1;//子节点深度是父节点加一
for(int i=0;i<20;i++)
{
f[u][i+1]=f[f[u][i]][i];//可以自己推导（就是乘个二
}
for(int i=head[u];i;i=cun[i].next)
{
int a=cun[i].v;//邻接表向后查询
if(a==fa)continue;//不查询父节点
f[a][0]=u;//a是u的子节点，向上跳2^0是父节点u
dfs(a,u);//递归
}
}
int LCA(int x,int y)
{
if(d[x]<d[y])swap(x,y);//后面方便
for(int i=20;i>=0;i--)//从后向前找，二进制拆分
{
if(d[f[x][i]]>=d[y])x=f[x][i];//如果深度大就向上跳到相等为止
if(x==y)return x;//如果同一深度时相等就相当于y是x的父节点
}
for(int i=20;i>=0;i--)
{
if(f[x][i]!=f[y][i])//向上跳不相等的话就向上跳
{
x=f[x][i];y=f[y][i];//继续
}
/*由于向上跳容易误判，所以我们选择向上跳到同一父节点时停止，最后输出父节点
向上跳无论如何都相等时就是同一父节点了*/
}
return f[x][0];//父节点便是LCA
}
int n,m,s;
int main()
{
cin>>n>>m>>s;//输入
for(int i=1;i<n;i++)
{
int x1,y1;
cin>>x1>>y1;
add(x1,y1);
add(y1,x1);//无向图需要双向添加边
}
dfs(s,0);
for(int i=1;i<=m;i++)
{
int x1,y1;
cin>>x1>>y1;
cout<<LCA(x1,y1)<<endl;//直接输出返回的就可以
}
return 0;
}