倍增LCA
LCA问题
在一棵树中求某两个结点的最近的公共祖先(LCA)
(两个结点向上去找到去最近的公共祖先)
LCA的大致流程
第一步——修正
将两个点修正到同一深度（并不是同一位置只是同一层）
在修正的过程中可能遇到的两种情况
- 两个点中的其中的一个点并非是其他那个点的祖先，这属于常规，且修正完后会去跑第二步
- 两个点中的其中一个点是另外一个结点的祖先，因而在修正后两个点会直接汇合。（不用再去执行第二部）
- 结论：在跑完修正这一步后，要做一个判断，去判断两个点是否为同一点。
第二步——并行
在深度修正后开始同时向根节点进发，直到在某一个结点汇合。
如果并行只是像乌龟一样一步步往根节点去爬，那么必然会收到一份叫TL的评测机礼品。
这里的话考虑用倍增的思想去优化LCA
倍增
二进制是一种数的进制，它可以用0和1来表示所有的数字。而将二进制的1可以给拆解出来转回十进制，也就是说，可以用2的幂次方的组合来表示所有的数字。
倍增与LCA问题的结合
\(f[i][j]数组\)
规定一个数组f[i][j]代表的是i往右跑\(2^{j}\)的位置。
所以有\(f[i][j]=i+2^j\)
同时\(i+2^j=i+2^{j-1}+2^{j-1}=(i+2^{j-1})+2^{j-1}=(f[i][j-1])+2^{j-1}=f[ f[i][j-1] ][j-1]\)
即\(f[i][j]=f[f[i][j-1]][j-1]\)
意思就是将i往右跑\(2^{j}\)的做法平摊成两次。
（这是一个递推式，或者可以说是简单的树形dp？我们只需要知道每个结点的直接父节点，我们就可以递推出所有的上几层的结点）
（f[i][j]=0的0代表的是跳不到这个位置，而在lca里这点就足够的。（在跳的过程只要不超过就行，即跳过去的深度是不小于另一个比较高的点））
试跳法
- ？借鉴了试除法去了这个名字，其实本质就是在二进制的状态下去还原这深度差
在两个点修正到同一深度后，从大到小枚举2的幂次方，如果当前能往上跳这个数字的层数，那就先跳先上去，否则继续向下枚举，当然了，如果在枚举的过程中，出现汇合的情况那么就跳出循环，返回答案。
其他
之所以有深度这些信息，是要构建出一棵树吧，而深度这个信息是相对根节点而言的，因而我们也是要去确定根节点是哪一个点，同时要利用好这个根节点去跑出所有结点的信息。
而结点和结点是通过线段来连接的，因而我们可以考虑利用一些建图方式去记录下来，比如链式前向星。
同时在跑dfs或者bfs之前开一个deep数组用来记录每一个结点的深度。
题目集
#include <bits/stdc++.h>
#define MEM(a,x) memset(a,x,sizeof(a))
#define W(a) while(a)
#define gcd(a,b) __gcd(a,b)
#define pi acos(-1.0)
#define PII pair<int,int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define MAX 1000005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define lowbit(x) (x&-x)
using namespace std;
const int N = 4E4+100;
int root;
int h[N],ne[N*2],e[N*2],n,idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dep[N],fa[N][25];
void bfs()
{
queue<int> q;
q.push(root);
dep[root]=1;
while(q.size())
{
int t=q.front();
q.pop();
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(dep[j])continue;
dep[j]=dep[t]+1;
fa[j][0]=t;
q.push(j);
for(int k=1;k<=20;k++)
{
fa[j][k]=fa[fa[j][k-1]][k-1];
}
}
}
}
int lca(int x,int y)
{
int defa=1;
/*********修正*********/
if(dep[x]>dep[y])//使得x永远在上面 ,x的深度最小
{
swap(x,y);
defa=2;
}
for(int i=20;i>=0;i--)
{
if(dep[ fa[y][i] ]>=dep[x])
y=fa[y][i];
}
if(x==y) return defa;
else return 0;
}
int main()
{
memset(h,-1,sizeof(h));
memset(dep,0,sizeof(dep));
memset(fa,0,sizeof(fa));
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(b==-1)
root=a;
else
add(a,b),add(b,a);
}
bfs();
int q;
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}