倍增求\(LCA\)

倍增基础

从字面意思理解，倍增就是“成倍增长”。

一般地，此处的增长并非线性地翻倍，而是在预处理时处理长度为\(2^n(n\in \mathbb{N}^+)\)的区间值。在这些预处理结果的基础上，我们可以进一步求出任意长度区间的答案。

比如区间最值问题\((RMQ)\)就可以使用倍增解决。对于每个起始点，预处理长度为\(2^n\)的区间最值。之后每段区间都可以以此求出，如：

\(f(1,7)=\max(f(1,4),f(3,7))\)

以上是最简单的一个举例。在计算机中，二进制的思想运用广泛。它能将复杂度中\(n\)因子化为\(log_2n\)，还可以使用位运算进行常数优化。

\(LCA\)

LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。——百度百科

定义很好理解。朴素的做法是预处理深度，将深度大的向上跳，再一起向上跳直到相遇。复杂度不好算，但绝对T飞。

注意到当两点相遇后，再如何跳都在同一个点上。所以就相当于\(LCA\)下不同，\(LCA\)上相同。这具有单调性，考虑二分。此处要对每一个点存储\(2^n\)级祖先，方法是预处理时递推。

我们记点i的\(2^k\)级祖先为\(fa[i][k]\)。

求解\(LCA\)的过程分为两步：一是提升到同一高度，二是同时向上跳。从最大的\(fa[x][log_2(depth[x])]\)开始逐次减半，相同则不跳，不同则跳。最终会到达\(LCA\)的下方。此时返回其中一个点的父亲，算法结束。

另外，预处理\(log_2\)的结果可以优化常数。

代码

#include
    
     #include
     
      #include
      
       using namespace std;int n,m,s,x,y;const int MAXN=500005;struct edge{    int to,next;}tree[MAXN*2];int depth[MAXN],lg2[MAXN],head[MAXN],fa[MAXN][25],eg,temp;int add(int from,int to){    tree[++eg].to=to;    tree[eg].next=head[from];    head[from]=eg;}int get_depth(int node,int father)//当前点和父亲{    depth[node]=depth[father]+1;    fa[node][0]=father;        for(int i=1;i<=lg2[depth[node]]-1;i++)        fa[node][i]=fa[fa[node][i-1]][i-1];//node的2^i级父亲等于它的  2^(i-1)级父亲的2^(i-1)级父亲    for(int i=head[node];i;i=tree[i].next)        if(tree[i].to!=father) get_depth(tree[i].to,node);}inline int LCA(int x,int y){    if(depth[x]
       
        depth[y])        x=fa[x][lg2[depth[x]-depth[y]]-1];//跳到相同高度    if(x==y) return x;    for(int i=lg2[depth[x]]-1;i>=0;i--)        if(fa[x][i]!=fa[y][i])            x=fa[x][i],y=fa[y][i];    return fa[x][0];//注意返回的不是x，是x的父亲}int main(){    scanf("%d %d %d",&n,&m,&s);    for(int i=1;i<=n-1;i++)        scanf("%d %d",&x,&y),add(x,y),add(y,x);//建树        for(int i=1;i<=MAXN;i++)        lg2[i]=lg2[i-1]+(1<