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

Goes · 2017-10-02 18:02:31 · 题解

听说大家早就会了rmq写lca

然而今天考试遇到了一个lca的题结果尴尬了

所以就来看看这个东西

感觉rmq写lca要好很多

无论是代码难度还是代码的美观2333

根据就是树的dfs序，父节点肯定比左边的子节点后入队，右边的子节点肯定比父节点后入队

那么可以推出最近公共祖先就应该是那个dfs序里深度小的那个

于是我们就开始用rmq求区间最小值

看到下面好像有人写了rmq写lca的题解

不过感觉我的代码要比他的好看，嗯，对，他也是这样认为的

洛谷好像没有rmq的裸题，如果有疑问的话是可以了解一下的

挺好玩的

好了，代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 500010
using namespace std;
#if 0

Writer: Goes && G.S.M. Just a game

Enjoy it

#endif
inline int read()
{
    char ch='*';
    while(!isdigit(ch=getchar()));
    int num=ch-'0';
    while(isdigit(ch=getchar()))num=num*10+ch-'0';
    return num;
}
struct ss{
    int to,nex;
}edge[N<<1];
int head[N],ecnt;
void add(int x,int y){
    edge[++ecnt]=(ss){y,head[x]};
    edge[++ecnt]=(ss){x,head[y]};
    head[x]=ecnt-1;head[y]=ecnt;
}
int q[N<<1],tot;
int f[N<<1][25];
int deep[N],p[N];
int n,m,root;
void DFS(int pos,int fa){
    q[tot++]=pos;p[pos]=tot-1;
    for(int i=head[pos];i;i=edge[i].nex)
    if(edge[i].to!=fa){
        deep[edge[i].to]=deep[pos]+1;
        DFS(edge[i].to,pos);
        q[tot++]=pos;
    }
    return;
}
void RMQ(){
    for(int i=0;i<tot;i++)    f[i][0]=q[i];
    for(int j=1;(1<<j)<=tot;j++)
        for(int i=0;i+(1<<j)-1<tot;i++)
        if(deep[f[i][j-1]]<deep[f[i+(1<<(j-1))][j-1]])
            f[i][j]=f[i][j-1];
        else f[i][j]=f[i+(1<<(j-1))][j-1];
}
void take(int x,int y)
{
    if(p[y]<p[x]) swap(x,y);
    int k=log(p[y]-p[x]+1)/log(2);
    if(deep[f[p[x]][k]]<deep[f[p[y]-(1<<k)+1][k]])
        printf("%d\n",f[p[x]][k]);
    else printf("%d\n",f[p[y]-(1<<k)+1][k]);
}
int main()
{
    n=read(),m=read(),root=read();
    for(int i=1;i<=n-1;i++)
        add(read(),read());
    DFS(root,0);RMQ();
    for(int i=1;i<=m;i++)
        take(read(),read());
    return 0;
}