题目链接

https://www.luogu.com.cn/problem/P3379

解题思路

ST表 + 欧拉序 。
通过欧拉序会发现根结点总在中间，而根结点是该段序列深度最小的点。
因此两个点的LCA，就是在该序列上两个点第一次出现的区间内深度最小的那个点。

细节见代码，主要是注意下标含义。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100;

int n,m,rt,Time,a,b;
int path[N<<1],pos[N<<1][20],dp[N],in[N],st[N<<1][20];
vector<int> e[N];

inline int read()
{
    int x;
    char ch='*';
    while(!isdigit(ch=getchar()));
    x=ch-'0';
    while(isdigit(ch=getchar())) x=(x<<3)+(x<<1)+ch-'0';
    return x;
}

void dfs(int x,int fa,int deep)
{
    path[++Time]=x;//入，记录欧拉序路径，路径的第Time个是第i个节点
    if(dp[x]==0) dp[x]=deep;//dp[i]表示i节点在树中的深度
    if(in[x]==0) in[x]=Time;//in[i]表示i节点第一次出现在欧拉序中的位置
    for(int i=0;i<e[x].size();i++)
    {
        if(fa==e[x][i]) continue;
        dfs(e[x][i],x,deep+1);
        path[++Time]=x;//出，记录欧拉序路径
    }
}

void CreateST()//创建st表
{
    for(int i=1;i<=Time;i++) st[i][0]=dp[path[i]],pos[i][0]=i;//pos两维的含义与st相同，记录的是区间深度最小的节点在欧拉序路径中的编号//初始化st表

    for(int j=1;(1<<j)<=Time;j++)
    for(int i=1;i+(1<<j-1)-1<=Time;i++)
    if(st[i][j-1]>st[i+(1<<j-1)][j-1]) 
    st[i][j]=st[i+(1<<j-1)][j-1],pos[i][j]=pos[i+(1<<j-1)][j-1];
    else st[i][j]=st[i][j-1],pos[i][j]=pos[i][j-1];
}

int Query(int l,int r)
{
    if(l>r) swap(l,r);
    int k=0;while(l+(1<<k+1)-1<=r)k++;
    return st[l][k]<st[r-(1<<k)+1][k]?path[pos[l][k]]:path[pos[r-(1<<k)+1][k]];//path下标的含义为欧拉序，path[i]的含义为欧拉序为i的节点的是哪个，所以pos要作为path的下标访问。 
}

int main()
{
    n=read(),m=read(),rt=read();
    for(int i=1;i<n;i++)
    {
        a=read(),b=read();
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(rt,-1,1);

    CreateST();

    while(m--)
    {
        a=read(),b=read();
        printf("%d\n",Query(in[a],in[b]));//Query传入的参数为在第一次在欧拉路径中出现的位置
    }

    return 0;
}