LCA(最近公共祖先)

洛谷最近公共祖先模板题
题目描述：给出一棵有 $N$N个节点的树，有 $M$M个询问，每个询问为 $u，v$u，v节点LCA
$N,M\&lt;=5e5$N,M<=5e5

倍增实现

复杂度： $O\left(nlogn\right)$O(nlogn)
此模板最小节点标号为1

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pr;
const int maxn = 5e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

inline int read() {
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
    return x;
}
//模板从下面开始
int to[maxn*2], nxt[maxn*2], head[maxn], cnt; //链式前向星存图
int N, M;
//vector<int> g[maxn]; //这道题卡常严重，故没有采用vector
int root; //根节点
int par[maxn][20], lg[maxn];
int d[maxn];

inline void add(int u, int v) { //链式前向星 加边
    to[++cnt]=v, nxt[cnt]=head[u], head[u]=cnt;
    to[++cnt]=u, nxt[cnt]=head[v], head[v]=cnt;
}

void dfs(int u, int p, int dep) { //dfs求节点深度
    par[u][0]=p;
    d[u]=dep;
    for(int i=head[u]; i; i=nxt[i])
        if(to[i]!=p) dfs(to[i],u,dep+1);
}

void pre() { //预处理出所有祖先
    for(int i=1; i<maxn; ++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i); //lg函数的预处理，这种做法可以不要
    dfs(root, -1, 0);
    for(int k=0; k+1<lg[N]; ++k)
        for(int v=1; v<=N; ++v)
            if(par[v][k]<0) par[v][k+1]=-1;
            else par[v][k+1]=par[par[v][k]][k];
}

int lca(int u, int v) {
    if(d[u]>d[v]) swap(u,v);
    for(int k=0; k<lg[N]; ++k) if((d[v]-d[u])>>k&1) v=par[v][k];
    if(u==v) return u;
    for(int k=lg[N]-1; k>=0; --k)
        if(par[u][k]!=par[v][k]) u=par[u][k], v=par[v][k];
    return par[u][0];
}

int main() {
    //ios::sync_with_stdio(false);
    N=read(), M=read(), root=read();
    for(int i=0; i<N-1; ++i) add(read(),read());
    pre(); //预处理不要忘了写，哈哈
    while(M--) printf("%d\n", lca(read(),read()));
}

tarjan的离线实现

复杂度： $O(n+q)$O(n+q)
但是在这道题上，反而要慢一些，有一个数据必须开O2才能过，并且开与不开速度差了一倍，可能是我自己写的不好吧。

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pr;
const int maxn = 5e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

int head[maxn], nxt[maxn*2], to[maxn*2], cnt;
int head1[maxn], nxt1[maxn*2], to1[maxn*2], cnt1, id[maxn*2]; //第二个链式前向星用来记录询问

int fa[maxn], ans[maxn];
bool vis[maxn];
int n, m, s;

inline int read() {
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
    return x;
}

inline void add(int u, int v) {
    to[++cnt]=v, nxt[cnt]=head[u], head[u]=cnt;
    to[++cnt]=u, nxt[cnt]=head[v], head[v]=cnt;
}

inline void add1(int u, int v, int i) {
    to1[++cnt1]=v, nxt1[cnt1]=head1[u], head1[u]=cnt1, id[cnt1]=i;
    to1[++cnt1]=u, nxt1[cnt1]=head1[v], head1[v]=cnt1, id[cnt1]=i;
}

int find(int x){ return x==fa[x]?x:find(fa[x]); }

void dfs(int u, int p){
    for(int i=head[u]; i; i=nxt[i])
        if(to[i]!=p) dfs(to[i],u), fa[to[i]]=u;
    for(int i=head1[u]; i; i=nxt1[i])
        if(vis[to1[i]]) ans[id[i]]=find(to1[i]);
    vis[u]=1;
}

int main(){
    n=read(), m=read(), s=read();
    for(int i=0; i<n-1; ++i) add(read(),read());
    for(int i=0; i<m; ++i) add1(read(),read(),i);
    for(int i=1; i<=n; i++) fa[i]=i;
    dfs(s,0);
    for(int i=0; i<m; i++) printf("%d\n", ans[i]);
}

RMQ(st表)

复杂度： $O\left(nlogn\right)$O(nlogn)
emmm，还没用过。

记录一下思路吧：

1. 预处理出dfs序，并记录每个节点第一次出现的位置fpos，随便采用一种方式求出来就行了，dfs序不唯一。
2. 再将dfs序的st表(min函数)处理好。
3. 对于询问(u,v),那么dfs序中fpos[u]与fpos[v]之间的最小节点就是LCA啦。

树剖实现

复杂度： $O\left(n\right)$O(n)
会写树剖肯定就会写这个啦，树剖几乎每个操作都涉及LCA，哈哈。