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;
;///顶点数
];
int Head[maxn], cnt;
int n, q, s;///点数、问询数、dfs起点
int fp[maxn]; int dfsLen;///每个顶点在欧拉序中第一次出现的位置、DFS序的长度（用做时间戳）
int id[maxn]; int idLen;///每个顶点在DFS序中访问次序（用于离散化）、id数组的长度
][];///跑ST表的dp数组（第二维应开到 ceil(log2(maxn<<1)) ）

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

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][] = tmp;
    ; i=Edge[i].nxt){
        int Eiv = Edge[i].v;
        if(Eiv == Fa) continue;
        dfs(Eiv, v, d);
        dp[++dfsLen][] = tmp;
    }
}

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

int LCA(int u, int v)
{
    if(fp[u] > fp[v]) swap(u, v);
    int L = fp[u], R = fp[v];
    )/log());
    <<k)+][k])];
}

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

    dfs(s, -);
    GetST();

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

2、树上倍增、复杂度 O(n+nlog2maxDep+mlog2maxDep), maxDep在最坏情况下等于n

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

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

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

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

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

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

inline void Doubling()
{
    ));
    ; j<=UP; j++){
        ; i<=n; i++){
            ] != -)
                Fa[i][j] = Fa[Fa[i][j-]][j-];
        }
    }
}

int LCA(int u, int v)
{
    ));
    if(dep[u] < dep[v]) swap(u, v);
    ; j--)
         && dep[Fa[u][j]] >= dep[v])
            u = Fa[u][j];

    if(u == v) return v;

    ; j--){
        if(Fa[u][j] != Fa[v][j]){
            u = Fa[u][j];
            v = Fa[v][j];
        }
    }

    ];
}

int main(void)
{
    scanf("%d %d %d", &n, &s, &q);
    ; 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\n", LCA(u, v));
    }
    ;
}

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

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

#include<bits/stdc++.h>
using namespace std;
;
];
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, -, sizeof(Head));
    memset(vis, false, sizeof(vis));
    cnt = ;
}

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;
    ; i=Edge[i].nxt){
        int Eiv = Edge[i].v;
        if(Eiv == f) continue;
        Tarjan(Eiv, v);
        Fa[Findset(Eiv)] = v;
    }
    vis[v] = true;
    ; 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);
    ; i<=m; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        AddEdge(u, v);
        AddEdge(v, u);
    }
    ; 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, -);
    ; i<q; i++) printf("%d\n", ans[i]);
    ;
}

4、树链剖分

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

巴特西

LCA模板 ( 最近公共祖先 )

最新文章

热门文章