LUOGU 3379 RMQ求LCA

LUOGU 3379
Description
求树上两点 $x,y$ 的LCA。

Input Format
第一行包含三个正整数 $N,M,S$ ，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 $N-1$ 行每行包含两个正整数 $x,y$ ，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边。
接下来 $M$ 行每行包含两个正整数 $a,b$ ，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

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

Sample Input

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

Sample Output

4
4
1
4
4

Constraints
对于 $100$ %的数据， $M \leq 5 \times 10^5,N \leq 5 \times 10^5$ 。

CCYOS
LCA板子题，RMQ做法可以做到常数回答询问。
前置技能

RMQ（ST表）

概念
时间戳 - 该结点dfs首次遍历到的序号，用 $dfn$ 记录。
欧拉序 - dfs遍历节点，节点的编号形成的序列，用 $ol$ 记录。（包括回溯）

在欧拉序上进行RMQ：
$depth[i][j]$ 表示从 $i$ 开始包括自身在内的 $2^j$ 个节点中的深度最小值，
$id[i][j]$ 表示与 $depth[i][j]$ 对应的节点编号，也就是这 $2^j$ 个节点的LCA。
LCA在 $ol[dfn[x]],ol[dfn[y]]$ 之间（闭区间）且是其中深度最小的节点，这是显然的：（设 $dfn[x] < dfn[y]$ ）
$(x,y)$ 有两种情况， $x$ 是 $y$ 的祖先，此时向下遍历一定会到达 $y$ ；
$x$ 不是 $y$ 的祖先，由于树上路径 $x,y$ 的唯一性，在到达 $x$ 后必然会退出 $x$ ，经过 $LCA(x,y)$ ，到达 $y$ 。

注意
a)处理RMQ数组时，欧拉序上的位置i须循环到 cnt - (1 << j) + 1。
j + (1 << i) - 1 <= cnt，这2^j个节点包括i自己；cnt表示获得的欧拉序的长度
b)ST表的输出，不能写成

while(l + (1 << k) <= r)++k;
printf("%d\n",id[l][k]);

会更新 $2 ^ k( \geq {|r - l|})$ 个子节点的LCA导致答案偏小。
code

#include<bits/stdc++.h>
using namespace std;

#define mxn 500005
int N,M,R,tot,cnt;
int dfn[mxn],ol[mxn << 1],dep[mxn],head[mxn];
int depth[mxn << 1][22],id[mxn << 1][22];
struct edge{
    int to,nxt;
}edg[mxn << 1];

inline int read(){
    char c = getchar();
    int ret = 0,fl = 1;
    for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

inline void add(int x,int y){
    edg[++tot].to = y;
    edg[tot].nxt = head[x];
    head[x] = tot;
}

inline void dfs(int u,int f){
    ol[++cnt] = u,dfn[u] = cnt,dep[u] = dep[f] + 1;
    for(int e = head[u];e;e = edg[e].nxt){
        int to = edg[e].to;
        if(to == f)
            continue;
        dfs(to,u);
        ol[++cnt] = u;
    }
}

int main(){
    N = read();M = read();R = read();
    for(int i = 1;i < N;++i){
        int x,y;
        x = read();y = read();
        add(x,y);add(y,x);
    }
    dfs(R,0);
    for(int i = 1;i <= cnt;++i)depth[i][0] = dep[ol[i]],id[i][0] = ol[i];
    for(int j = 1;j <= 22;++j)
        for(int i = 1;i <= cnt - (1 << j) + 1;++i){
            if(depth[i][j - 1] > depth[i + (1 << (j - 1))][j - 1])
                depth[i][j] = depth[i + (1 << (j - 1))][j - 1],
                id[i][j] = id[i + (1 << (j - 1))][j - 1];
            else 
                depth[i][j] = depth[i][j - 1],
                id[i][j] = id[i][j - 1];
        //  cout<<"          "<<i<<" "<<j<<" "<<id[i][j]<<endl;
        }
    for(int i = 1;i <= M;++i){
        int l,r;l = read();r = read();
        l = dfn[l],r = dfn[r];
        if(r < l)swap(l,r);
        int k = 0;
        while(l + (1 << k) <= r)++k;
        k--;
        if(depth[l][k] < depth[r - (1 << k) + 1][k])printf("%d\n",id[l][k]);//!!!
        else printf("%d\n",id[r - (1 << k) + 1][k]);
    }
    return 0;
}

LUOGU 3379 RMQ求LCA

推荐阅读更多精彩内容