二进制分组与LCA

发表于 | 分类于

本文介绍倍增法求LCA

例题HDOJ2586

例题题意

抽象一下 题目给了一棵树 要求给出的两个节点之间的简单路径的距离
在给出算法之前 我们先介绍一下LCA

LCA的含义

LCA(Lowest Common Ancestor)最近公共祖先 指的是在一棵树中距离某两个节点最近的祖先节点（顾名思义）

例题分析

题意很容易理解 也不难想到一般的暴力做法 比如跑一遍最短路啥的(ps:这题最短路是能过的 数据有点水)
不过我们这里用LCA来解决
容易想到的做法是：
记p是u和v节点的LCA 那么答案就是dis(u,p)+dis(v,p) 这是很容易理解的
那么下一步我们就是求u v节点的LCA

LCA的实现

首先我们方法有很多 比如暴力

暴力实现

u节点和v节点同时向自己的父亲节点跳 并打vis标记 如果某一个节点p被重复打标记 那么这个p就是LCA
然而 暴力的方法理解起来简单 但也有他的局限性 首先 这个方法最坏是O(n)的（考虑一条链状的树）时间复杂度很高 如果询问组数比较多 大部分情况是过不了题的

优化

回顾一下背包问题：
有n种物品$a_1 a_2…a_n$每种物品都有不同的数量$b_1 b_2…b_n$和不同的价值$c_1 c_2…c_n$ 问 容量为m的背包最多能装多少价值的物品？
关于背包问题的解法就不做具体介绍了(dp) 关键是这里的一个关键的优化采用了二进制分组的想法：
对物品$a_i$分组 $1/2/4/8/…/2^n$ 捆绑每一个组的物品变成一个新的物品 然后把问题规约成一个01背包问题 这比直接把原问题当作01背包来处理会快很多
原理是这样的：
每一个十进制数可以表示成一系列2幂次数的和 因为$x=(\overline{b_0b_1...b_n})_{2}=\sum_{i=0}^n{b_i\cdot2^i}$
那么在LCA问题下 每次只要往上跳$2^i$的距离即可 复杂度降到了对数级别

具体实现

  1. 一遍dfs求出每一个节点的深度depth[] 并预处理出up[][]数组 up[i][j]表示i节点往上跳$2^j$的节点
  2. 处理询问 假设节点u的深度大于v的深度 先把u节点跳到和v相同深度
    1. 如果u==v 说明询问的两个节点在同一条树链上 直接返回u 算法结束
    2. 如果u!=v 说明询问的两个节点不在同一条树链上 u v开始同时向上跳 注意一点 当两个节点向上跳$2^i$以后位于不同的节点才执行跳的操作(原因后面会说)
  4. 此时u和v同时向上跳1个节点就达到LCA节点了 算法结束

整个算法过程中向上跳的操作 都从长距离向短距离跳 即先跳$2^i$ 再跳$2^{i-1}$ 再跳$2^{i-2}$…

算法中的细节

Q1:
为什么3.2.中说“当两个节点向上跳$2^i$以后位于不同的节点才执行跳的操作”？
A1:
首先我们在向上跳的时候不能跳过lca节点了 不然找不到lca了
如果up[u][i]==up[v][i]就说明跳过了或者到达了lca节点

Q2:
为什么第四步中u和v同时向上跳1个节点就到达lca了？
A2:
这是一个小trick 其实这里用while循环一个一个往上跳也是没有问题的 不过还是循环体内顶多执行一次
假设LCA和u(v)的距离为c 注意到 c-1一定可以被二进制分组 那么遵循从长距离向短距离跳的原则 并且u和v不会跳到LCA及LCA上面去 那么过程中一定会跳到LCA节点的儿子节点 并在这里停住不会再往上跳直到3.结束 因此 4.中u和v直接向上跳1个节点就是LCA了

Q3:
怎么处理up数组？
A3:
由于$2^i=2^{i-1}+2^{i-1}$
假设在处理up[v]数组的时候我们预先已经处理好了up[ansestor of v]数组 那么up[v][i]=up[up[v][i-1]][i-1]

Q4:
预处理？
A4:
在询问组数比较多的情况下 预处理是必须的 预处理的复杂度是$O(n)$->即dfs的复杂度 在之后向上跳的复杂度是$O(1)$的
当然如果只有一次询问 请选择直接用以上说的直接暴力做法 复杂度是$O(n)$的 和预处理复杂度相差无几 但是码短

算法复杂度

假设一共是n个节点 m组询问
dfs的复杂度是$O(n)$ 处理每一组询问的复杂度是$O(\log n)$
所以总复杂度是$O(n+m\log n)$

例题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>

using namespace std;
const int N=40000+10;
const int TP=32;

struct Edge{
    int from,to,cost;
    Edge(int from,int to,int cost):from(from),to(to),cost(cost){}
    Edge(){}
};

int n,m;
vector<Edge> edges;
vector<int> g[N];
int depth[N],up[N][TP];
int len[N][TP];

inline void clearall(){
    for(int i=1;i<=n;i++) g[i].clear();
    edges.clear();
}

inline void addedge(int from,int to,int cost){
    edges.push_back(Edge(from,to,cost));
    g[from].push_back(edges.size()-1);
}

//题目要求两点间距 所以在dfs的时候追加预处理len数组
//len[i][j]表示i节点向上跳2^j的距离
void dfs(int v,int fa){
    up[v][0]=fa;
    for(int i=1;i<TP;i++){
        if(up[v][i-1]==-1) break;
        up[v][i]=up[up[v][i-1]][i-1];
        len[v][i]=len[v][i-1]+len[up[v][i-1]][i-1];
    }
    for(int i=0;i<g[v].size();i++){
        auto &e=edges[g[v][i]];
        if(e.to!=fa){
            depth[e.to]=depth[v]+1;
            len[e.to][0]=e.cost;
            dfs(e.to,v);
        }
    }
}

inline void init(){
    memset(up,-1,sizeof(up));
    memset(len,0,sizeof(len));
    depth[1]=1;
    dfs(1,-1);
}

inline void ask(int u,int v){
    int ans=0;
    if(depth[u]<depth[v]) swap(u,v);
    for(int i=TP-1;i>=0;i--){
        if(up[u][i]==-1) continue;
        if(depth[u]>depth[v]&&depth[up[u][i]]>=depth[v]) ans+=len[u][i],u=up[u][i];
    }
    /*
    //判断同树链
    if(u==v){
        cout<<ans<<endl;
        return;
    }
    */
    for(int i=TP-1;i>=0;i--){
        if(up[u][i]==-1||up[v][i]==-1) continue;
        if(up[u][i]!=up[v][i]){
            ans+=len[u][i]+len[v][i];
            u=up[u][i];
            v=up[v][i];
        }
    }
    //这里判u!=v的原因是如果他们如果在同一条树链上
    //就不需要往上跳了
    //也可以选择在上面判断
    if(u!=v){
        ans+=len[u][0]+len[v][0];
    }
    cout<<ans<<endl;
}

int main(){
    int cas;
    cin>>cas;
    while(cas--){
        scanf("%d %d",&n,&m);
        clearall();
        for(int i=1;i<n;i++){
            int from,to,cost;
            scanf("%d %d %d",&from,&to,&cost);
            addedge(from,to,cost);
            addedge(to,from,cost);
        }
        init();
        while(m--){
            int from,to;
            scanf("%d %d",&from,&to);
            ask(from,to);
        }
    }
    return 0;
}