之前学习过一次lca，是用暴力，倍增，tarjan离线处理的。
之前就知道lca还有其他两种写法，不过那个时候还不会树剖，就没学。
今天学习树剖之后，发现lca树剖写法不就是个裸的树剖吗。
预处理 O（n） 查询logn 比倍增还优秀一点。
今天就补上没学的那两种lca的写法了。

P3379 【模板】最近公共祖先（LCA）：

题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式
第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。

接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。

输出格式
输出包含M行，每行包含一个正整数，依次为每一个询问的结果。

输入输出样例
输入 #1 复制
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出 #1 复制
4
4
1
4
4
说明/提示
时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

一、树剖：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=500500;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int d[maxn],f[maxn],son[maxn],si[maxn];
int rk[maxn],id[maxn],top[maxn];
int tot=1,cnt=0;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs1(int x,int fa)
{
    int max_son=0;
    si[x]=1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        d[y]=d[x]+1;
        f[y]=x;
        dfs1(y,x);
        si[x]+=si[y];
        if(si[y]>max_son) max_son=si[y],son[x]=y;
    }
}

void dfs2(int x,int t)
{
    top[x]=t;
    id[x]=++cnt;
    rk[cnt]=x;
    if(!son[x]) return ;
    dfs2(son[x],t);
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y!=son[x]&&y!=f[x])
            dfs2(y,y);
    }
}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    return id[x]>id[y]?y:x;
}

int main(void)
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs1(s,0);
    dfs2(s,s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}

二、dfs+st算法：
nlogn预处理，O（1）查询。
log函数的效率较高，可以即用即调用，不过可以O（n）处理出来所有的log2（len）
①
前置知识，RMQ（区间最值）的ST算法。
P3865 【模板】ST表：
题目背景
这是一道ST表经典题——静态区间最大值

请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)

题目描述
给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。

输入格式
第一行包含两个整数 N, M 分别表示数列的长度和询问的个数。

第二行包含 N 个整数依次表示数列的第 i 项。

接下来 M行，每行包含两个整数 l, r，表示查询的区间为 [ l, r]
输出格式
输出包含 M行，每行一个整数，依次表示每一次询问的结果。

输入输出样例
输入 #1 复制
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
输出 #1 复制
9
9
7
7
9
8
7
9
n<=1e5，m<=1e6

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=101000;
int f[maxn][20],a[maxn], _log[maxn];
int n,m;
void ST(void)
{
    for(int i=1;i<=n;i++)
        f[i][0]=a[i],_log[i]=log(i)/log(2);
    int t=_log[n]+1;
    for(int j=1;j<=t;j++)
    {
        for(int i=1;i<=n-(1<<j)+1;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
}

int get_max(int l,int r)
{
    int k=_log[r-l+1];
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    ST();
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",get_max(x,y));
    }
    return 0;
}

②dfs+st
dfs这棵树，得到一个序列。
这个序列是，每个节点第一次被访问时做标记，每个节点每访问完一个儿子时做标记。
经证明，这样的dfs序的长度为2*n-1。（猜测证明法）
处理出每个节点在dfs树上的深度，第一次访问这个节点时dfs的标号。
对于节点x，y，id（x）与id（y）之间dfs的标号深度最小的就是它们的lca。
以上洛谷的求lca的题目为例，代码如下。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=501000;
int head[maxn],ver[maxn<<1],nt[maxn<<1];
int d[maxn],id[maxn],rk[maxn<<1],dd[maxn<<1];
int f[maxn<<1][21],_log[maxn<<1];
int tot=1,cnt=0;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs(int x,int fa)
{
    id[x]=++cnt;rk[cnt]=x;dd[cnt]=d[x];
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y==fa) continue;
        d[y]=d[x]+1;
        dfs(y,x);
        rk[++cnt]=x,dd[cnt]=d[x];
    }
}

void ST(void)
{
    for(int i=1;i<=cnt;i++)
        f[i][0]=i,_log[i]=log(i)/log(2);
    int t=_log[cnt]+1;
    for(int j=1;j<=t;j++)
    {
        for(int i=1;i<=cnt-(1<<j)+1;i++)
            f[i][j]=dd[f[i][j-1]]<dd[f[i+(1<<(j-1))][j-1]]?f[i][j-1]:f[i+(1<<(j-1))][j-1];

    }
}

int lca(int x,int y)
{
    if(id[x]>id[y]) swap(x,y);
    x=id[x],y=id[y];
    int k=_log[y-x+1];
    return dd[f[x][k]]<dd[f[y-(1<<k)+1][k]]?rk[f[x][k]]:rk[f[y-(1<<k)+1][k]];
}

int main(void)
{
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    int x,y;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(s,0);
    ST();
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}