LCA（最近公共祖先）-倍增算法

例题啥的还不完善，等有机会再整理吧

/*少说话，多做事*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
//#include<bits/stdc++.h>
//ios::sync_with_stdio(0);
//cin.tie(0);
//cout.tie(0);
typedef long long ll;

using namespace std;

/*
 第一行：n (n头牛）（1-5e4）    Q（询问次数）1-2e5

 接下来n行：牛的高度(1-2e5)

 接下来Q行 Q次询问
 m行（m次询问）i j ： 表示i与j之间的距离是多少

 DFS+ST：将树看成一个无向图，u和v的公共祖先一定在u和v之间的最短路径上，
 （1）DFS：从树T的根开始，进行深度优先遍历（将树看成一个无向图），并记录好每次到达的顶点。
 由于每条边恰好经历两次，所以一共记录了2n-1个点，用E[1~2n-1]来表示
 （2）计算R：用R[i]表示E数组中第一个值为i的元素下标
 如果R[u]<R[v],DFS访问的顺序是E[R[u],R[u]+1,....R[v]].
 虽然其中包含u的后代，但深度最小的还是u与v的公共祖先
 （3）RMQ：计算RMQ
 当R[u]>=R[v]时，LCA[T,u,v]=RMQ(L,R[v],R[u])
 否则：          LCA[T,u,v]=RMQ(L,R[u],R[v])
 */



inline int read()
{
    int f=1,x=0;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f*=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N=5e5+5;
int a[N],n,m,s,to[N<<1],nxt[N<<1],grd[N][23],d[N],cnt;

int head[N];
void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;//邻接表
}

void dfs(int x,int fa) //根节点 0
{
    int i;
    grd[x][0]=fa;//父节点（根节点x的父亲节点为0）
    d[x]=d[fa]+1;//x节点的深度是他的父亲节点的深度+1

    for(i=1;i<21;i++) //其实到本题19就可以了，习惯到20整一点哈哈哈
    {
        grd[x][i]=grd[grd[x][i-1]][i-1];//预处理grd数组
    }

    for(i=head[x];i;i=nxt[i]) //对x节点进行遍历
    {
        if(to[i]!=fa) dfs(to[i],x); //如果终点不是他的父亲节点，那么就进行更新
    }
}

int lca(int x,int y)
{
    int i;
    if(d[x]<d[y])  //将x的深度调成更深的，然后将其跳到跟y一样深度
    {
        swap(x,y);
    }
    for(i=20;i>=0;i--) //从大到小枚举 （肯定可以跳到相同深度）
    {
        if(d[y]<=d[x]-(1<<i))//1<<i就是2^i,也可以预处理成数组
        {
            x=grd[x][i];
        }
    }
    if(x==y) return x;//当y是x的祖先时

    for(i=20;i>=0;i--)
    {
        if(grd[x][i]!=grd[y][i]) //如果不相等的话就往上跳，for循环结束后，可以确定再向上跳一次就是两者的父亲节点
        {
            x=grd[x][i];
            y=grd[y][i];//一起往上跳
        }
    }
    return grd[x][0];   //返回父节点 (就是再向上跳一次就是父亲节点）
}

/*邻接表 + 预处理grd数组 + 跳到相同深度 + 一起往上跳*/

int main()
{
    n=read();m=read();s=read(); //树的节点个数 、 询问的个数 和 树根节点的序号
    int i,j,x,y;
    for(i=1;i<n;i++)
    {
        x=read();y=read();
        add(x,y);
        add(y,x);//邻接表（也是跟链式向前星）
    }
    dfs(s,0);//预处理

    for(i=1;i<=m;i++)
    {
        x=read();y=read();
        printf("%d\n",lca(x,y));
    }

    return 0;
}