倍增求lca

佚名 6年前 (2019-04-18) 随笔 1452人围观抢沙发百度已收录

对于每个节点v，记录anc[v][k]，表示从它向上走2^k步后到达的节点（如果越过了根节点，那么anc[v][k]就是根节点）。

dfs函数对树进行的dfs，先求出anc[v][0]，再利用anc[v][k] = anc[anc[v][k - 1]][k - 1] （从v向上2^k步即为从v向上2^{(k - 1)}步再向上2^{(k - 1)}步）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

求出其他anc[v][k]的值

lca(u, v)函数寻找u和v的lca，首先把u和v调整到一个高度。如果此时u和v重合，那么这就是我们要找的lca，如果他们补充和，就不断的寻找一个最小的k，使得

anc[u][k] = anc[v][k]

int anc[maxn][20], deep[maxn];

int dfs(int u, int fa)
{
    for(int i = 1; i < 20; i++)
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for(int i = head2[u]; i != -1; i = Edge[i].next)
    {
        int v = Edge[i].v;
        if(v == fa || deep[v]) continue;
        anc[v][0] = u;
        deep[v] = deep[u] + 1;
        dfs(v, u);
    }
}

int lca(int u, int v)
{
    if(deep[u] < deep[v]) swap(u, v);
    for(int i = 20 - 1; i >= 0; i--)
        if(deep[anc[u][i]] >= deep[v])
            u = anc[u][i];

    for(int i = 20 - 1; i >= 0; i--)
    {
        if(anc[u][i] != anc[v][i])
        {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    if(u == v) return u;
    return anc[u][0];
}