模板集合(持续更新)

倍增求\(LCA\)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define ll long long
using namespace std;

template <typename T> void in(T &x) {
    x = 0; T f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch)) {x = 10*x+ch-'0'; ch = getchar();}
    x *= f;
}

template <typename T> void out(T x) {
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) out(x/10);
    putchar(x%10+'0');
}
//---------------------------------------------------------------

const int N = 5e5+7;

int n,m,rt;
struct edge {
    int v,nxt;
    edge(int v = 0,int nxt = 0):v(v),nxt(nxt){}
}e[N<<1]; int head[N],e_cnt;

void add(int u,int v) {
    e[++e_cnt] = edge(v,head[u]); head[u] = e_cnt;
}

int fa[N][21],dep[N];
void dfs(int u,int f) {
    dep[u] = dep[f]+1;
    fa[u][0] = f;
    for(int i = 1;(1<<i) <= dep[u]; ++i) fa[u][i] = fa[fa[u][i-1]][i-1];
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v; if(v == f) continue;
        dfs(v,u);
    }
}

int Q_lca(int x,int y) {
    if(dep[x] < dep[y]) swap(x,y);
    int d = dep[x]-dep[y];
    for(int i = 0;(1<<i) <= d; ++i) {
        if(d&(1<<i)) x = fa[x][i];
    }
    if(x == y) return x;
    for(int i = 20;i >= 0; --i) {
        if(fa[x][i] == fa[y][i]) continue;//debug [i] -> [0]
        x = fa[x][i]; y = fa[y][i];
    }
    return fa[x][0];
}

int main() {
    int i,u,v; in(n); in(m); in(rt);
    for(i = 1;i < n; ++i) {
        in(u); in(v);
        add(u,v); add(v,u);
    }
    dfs(rt,0);
    while(m--) {
        in(u); in(v);
        out(Q_lca(u,v)),putchar('\n');
    }
    return 0;
}