LUOGU 3379 RMQ求LCA

LUOGU 3379
Description
求树上两点的LCA。

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

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

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
对于%的数据，。

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

• RMQ（ST表）

1. 概念
   时间戳 - 该结点dfs首次遍历到的序号，用记录。
   欧拉序 - dfs遍历节点，节点的编号形成的序列，用记录。（包括回溯）
2. 在欧拉序上进行RMQ：
   表示从开始包括自身在内的个节点中的深度最小值，
   表示与对应的节点编号，也就是这个节点的LCA。
   LCA在之间（闭区间）且是其中深度最小的节点，这是显然的：（设）
   有两种情况，是的祖先，此时向下遍历一定会到达；
   不是的祖先，由于树上路径的唯一性，在到达后必然会退出，经过，到达。

注意
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]);

会更新个子节点的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;
}