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

https://www.luogu.org/problem/P3379

题目描述

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

输入格式

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

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

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

输出格式

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

---

 

倍增法log(2)级

fa[x][i]表示从x向上爬(1<<i)次到达的祖先，即f[x][0]为向上爬(1<<0)=1次为x的父节点

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

#define ri register int
#define u int
#define NN 500005
#define MM 500005

namespace fast {

    inline u in() {
        u x(0),f(1);
        char s=getchar();
        while(s<‘0‘||s>‘9‘) {
            if(s==‘-‘) {
                f=-1;
            }
            s=getchar();
        }
        while(s>=‘0‘&&s<=‘9‘) {
            x=(x<<1)+(x<<3)+s-‘0‘;
            s=getchar();
        }
        return x*f;
    }

}

using fast::in;

namespace all {

    u N,M,S,mxd,d[NN],fa[NN][20];

    u cnt,h[NN];
    struct node {
        u to,next;
    } a[MM<<1];
    inline void add(const u &x,const u &y) {
        a[++cnt].next=h[x],a[cnt].to=y,h[x]=cnt;
    }

    void dfs(const u &x,const u &prt,const u &deep) {
        d[x]=deep,fa[x][0]=prt,mxd=std::max(mxd,deep);
        for(ri i(h[x]); i; i=a[i].next) {
            u _y(a[i].to);
            if(_y^prt) {
                dfs(_y,x,deep+1);
            }
        }
    }

    u climb(u x,u y) {
        if(d[x]>d[y]) {
            std::swap(x,y);
        }
        u _k((u)(log(d[y])/log(2)));
        for(ri i(_k); i>=0; --i) {
            if(d[y]-(1<<i)>=d[x]) {
                y=fa[y][i];
            }
        }
        if(x==y) return x;
        for(ri i(_k); i>=0; --i) {
            if(fa[x][i]^fa[y][i]) {
                x=fa[x][i],y=fa[y][i];
            }
        }
        return fa[x][0];
    }

    inline void solve() {
        N=in(),M=in(),S=in();
        for(ri i(1); i<N; ++i) {
            u _a(in()),_b(in());
            add(_a,_b),add(_b,_a);
        }
        dfs(S,0,1);
        for(ri j(1); mxd-(1<<j)>=1; ++j) {
            for(ri i(1); i<=N; ++i) {
                fa[i][j]=fa[fa[i][j-1]][j-1];
            }
        }
        for(ri i(1); i<=M; ++i) {
            u _a(in()),_b(in());
            printf("%d\n",climb(_a,_b));
        }
    }

}

int main() {

    //freopen("x.txt","r",stdin);
    all::solve();

}