LCA(ST倍增)

时间复杂度：

dfs树，求st表(状态数组f)：O(NlgN)

处理M个查询：O(MlgN)

总：O((M+N)lgN)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=500010;
struct edge{ int t; edge * nxt; edge(int to, edge * next){ t=to, nxt=next; } };
edge * h[maxn];
void add(int u, int v) { h[u]=new edge(v, h[u]); }
int N, M, S, fa[maxn], L[maxn], f[maxn][20];//S为根节点，fa为父亲数组，L记录结点深度，f为状态数组 inline int read(){
    int s=0, w=1; char ch=getchar();
    while(ch<'0' || ch>'9' ){ if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0' && ch<='9'){ s=s*10+ch-'0';    ch=getchar(); }
    return s*w;
}void dfs(int x){//在dfs过程中计算出每个节点的深度L、father
    L[x]=L[fa[x]]+1;
    f[x][0]=fa[x];
    for(int i=1; (1<<i)<=L[x]; i++)//使用倍增思想[ST]计算出当前结点的2^i代祖先
        f[x][i]=f[f[x][i-1]][i-1];
    for(edge * p=h[x]; p; p=p->nxt){
        if(p->t==fa[x]) continue;
        fa[p->t]=x;
        dfs(p->t);
    }
}// void prep(){//这是另一种形式dp计算所有节点的2^k祖宗
// int max_k=log(N)/log(2);
// for(int i=1; i<=N; i++)//依赖于dfs得到的fa数组作为初始状态
// f[i][0]=fa[i];
// for(int k=1; k<max_k; k++){//状态转移的时间复杂度为O(NlgN)
// for(int i=1; i<=N; i++){
// if((L[i]-(1<<k))>0)
// f[i][k]=f[f[i][k-1]][k-1];//但倍增计算放在dfs里面是最巧妙、高效的
// }
// }
// }int lca(int x, int y){
if(x==y)return x;//!!!!!!!!!!!!!非常重要，不用解释!!!!!!!!!!
    if(L[x]<L[y])swap(x, y);//如果x比y浅，交换，使得x比y深
    int t=log(L[x]-L[y])/log(2);//计算x，y相差的层数，x最大可以向上跳2^t层
    for(int i=t; i>=0; i--){//从x位置以二进制的方式向上跳
        if(L[f[x][i]]>=L[y])x=f[x][i];
        if(x==y)return x;
    }
    t=log(L[x])/log(2);//距离树根，最多可以向上跳2^t层
    for(int i=t; i>=0; i--)//从x， y位置以二进制的方式一同向上跳
        if(f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];//father不一样，继续跳
    return f[x][0];
}int main(){
    N=read(); M=read(); S=read();
    for(int i=1, x, y; i<N; i++){ x=read(); y=read(); add(x, y); add(y, x); }
    dfs(S);
    for(int i=1, a, b; i<=M; i++){ a=read(); b=read(); printf("%d\n", lca(a, b)); }
    return 0;
}