LCA模板 ( 最近公共祖先 )

LCA 有几种经典的求取方法、这里只给出模板，至于原理我完全不懂。

1、RMQ转LCA、复杂度O(n+nlog2n+m)

大致就是 DFS求出欧拉序 => 对欧拉序做ST表 => LCA(u, v) 即为 u、v 最先出现在欧拉序中的编号之间的最小值。

因为 LCA 的子树中必定有一个节点是 u，一个是 v，而且必定在两个节点到根节点的唯一路径上。

例如有欧拉序列 1 2 1 3 4 3 1 则 LCA(2, 3) == 1 、首次出现 2 的下标是 2、首次出现 3 的下标是 4、则 LCA 就是下标 2~4 之间的最小值即 1

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 10;///顶点数
struct EDGE{ int v, nxt, w; }Edge[maxn<<1];
int Head[maxn], cnt;
int n, q, s;///点数、问询数、dfs起点
int fp[maxn]; int dfsLen;///每个顶点在欧拉序中第一次出现的位置、DFS序的长度（用做时间戳）
int id[maxn]; int idLen;///每个顶点在DFS序中访问次序（用于离散化）、id数组的长度
int dp[maxn<<1][21];///跑ST表的dp数组（第二维应开到 ceil(log2(maxn<<1)) ）

inline void init()
{
    memset(dp, 0, sizeof(dp));
    memset(Head, -1, sizeof(Head));
    cnt = 0; idLen = dfsLen = 0;
}

inline void AddEdge(int from, int to, int weight)
{
    Edge[cnt].v = to;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}


void dfs(int v, int Fa)
{
    int tmp;
    id[tmp = ++idLen] = v;
    dp[fp[v] = ++dfsLen][0] = tmp;
    for(int i=Head[v]; i!=-1; i=Edge[i].nxt){
        int Eiv = Edge[i].v;
        if(Eiv == Fa) continue;
        dfs(Eiv, v, d);
        dp[++dfsLen][0] = tmp;
    }
}

void GetST()
{
    for(int j=1; (1<<j)<=dfsLen; j++){
        for(int i=1; i+(1<<j)-1<=dfsLen; i++){
            dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
        }
    }
}

int LCA(int u, int v)
{
    if(fp[u] > fp[v]) swap(u, v);
    int L = fp[u], R = fp[v];
    int k = (int)(log(R-L+1)/log(2));
    return id[min(dp[L][k], dp[R-(1<<k)+1][k])];
}

int main(void)
{
    scanf("%d %d %d", &n, &s, &q);
    for(int i=1; i<n; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        AddEdge(u, v);
        AddEdge(v, u);
    }

    dfs(s, -1);
    GetST();

    while(q--){
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d
", LCA(u, v));
    }
    return 0;
}

View Code

2、树上倍增、复杂度 $O (n + n l o g_{2} d + m l o g_{2} d)$

大致就是 DFS求出每个节点的深度、父亲节点这两个信息 => 通过倍增求出每个节点向根节点方向走 2^j 所能到达节点是什么

=> LCA(u, v) 就可以通过预先处理好的倍增数组先移动u、v使其深度一样、然后再一起 2^j 向上跳，直到跳转到 LCA

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;///顶点的数目
struct EDGE{ int v, nxt, w; }Edge[maxn<<1];
int Head[maxn], cnt;
int dep[maxn], maxDep;///每个点的深度、最深点的深度
int Fa[maxn][21];///倍增记录数组（ Fa[i][j] 从 i 号节点开始走 2^j 步能到达的点 )
int n, m, s, q;///点、边、dfs起点、问询数

inline void init()
{
    memset(Head, -1, sizeof(Head));
    memset(Fa, -1, sizeof(Fa));
    cnt = 0; maxDep = 0;
}

inline void AddEdge(int from, int to)
{
    Edge[cnt].v = to;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}

void dfs(int v)
{
    if(Fa[v][0] != -1)
        maxDep = max(maxDep, dep[v] = dep[Fa[v][0]]+1);
    for(int i=Head[v]; i!=-1; i=Edge[i].nxt){
        int Eiv = Edge[i].v;
        if(Eiv == Fa[v][0]) continue;
        Fa[Eiv][0] = v;
        dfs(Eiv);
    }
}

inline void Doubling()
{
    int UP = (int)(log(maxDep)/log(2));
    for(int j=1; j<=UP; j++){
        for(int i=1; i<=n; i++){
            if(Fa[i][j-1] != -1)
                Fa[i][j] = Fa[Fa[i][j-1]][j-1];
        }
    }
}

int LCA(int u, int v)
{
    int UP = (int)(log(maxDep)/log(2));
    if(dep[u] < dep[v]) swap(u, v);
    for(int j=UP; j>=0; j--)
        if(Fa[u][j] != -1 && dep[Fa[u][j]] >= dep[v])
            u = Fa[u][j];

    if(u == v) return v;

    for(int j=UP; j>=0; j--){
        if(Fa[u][j] != Fa[v][j]){
            u = Fa[u][j];
            v = Fa[v][j];
        }
    }

    return Fa[u][0];
}

int main(void)
{
    scanf("%d %d %d", &n, &s, &q);
    for(int i=1; i<n; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        AddEdge(u, v);
        AddEdge(v, u);
    }

    dfs(s);
    Doubling();

    while(q--){
        int u, v;
        scanf("%d %d", &u, &v);
        printf("%d
", LCA(u, v));
    }
    return 0;
}

View Code

3、Tarjan算法( 离线 )、复杂度 O(n+m+nα(n))

大致就是算了给个链接吧 Tarjan求LCA

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
struct EDGE{ int v, nxt, w; }Edge[maxn<<1];
struct Query{ int v, id;
    Query(){};
    Query(int _v, int _id):v(_v),id(_id){};
}; vector<Query> q[maxn];

int Head[maxn], cnt;
int Fa[maxn];///并查集数组
int ans[maxn];///问询数数组大小要注意一下、不一定是 maxn
bool vis[maxn];///Tarjan算法中的标记数组
int n, m, s, qNum;///点、边、Tarjan递归起点、问询数

inline void init()
{
    memset(Head, -1, sizeof(Head));
    memset(vis, false, sizeof(vis));
    cnt = 0;
}

inline void AddEdge(int from, int to)
{
    Edge[cnt].v = to;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}

int Findset(int x)
{
    int root = x;
    while(Fa[root] != root) root = Fa[root];

    int tmp;
    while(Fa[x] != root){
        tmp = Fa[x];
        Fa[x] = root;
        x = tmp;
    }

    return root;
}

void Tarjan(int v, int f)
{
    Fa[v] = v;
    for(int i=Head[v]; i!=-1; i=Edge[i].nxt){
        int Eiv = Edge[i].v;
        if(Eiv == f) continue;
        Tarjan(Eiv, v);
        Fa[Findset(Eiv)] = v;
    }
    vis[v] = true;
    for(int i=0; i<q[v].size(); i++){
        if(vis[q[v][i].v])
            ans[q[v][i].id] = Findset(q[v][i].v);
    }
}

int main(void)
{
    init();
    scanf("%d %d %d %d", &n, &m, &s, &qNum);
    for(int i=1; i<=m; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        AddEdge(u, v);
        AddEdge(v, u);
    }
    for(int i=0; i<q; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        q[u].push_back(Query(v, i));
        q[v].push_back(Query(u, i));
    }
    Tarjan(s, -1);
    for(int i=0; i<q; i++) printf("%d
", ans[i]);
    return 0;
}

View Code

4、树链剖分

并不会树剖，以后再补......