倍增算法 模板

本文介绍的是LCA在线算法中的倍增算法。

---

不知道LCA定义？请戳这儿

---

算法理论

• 朴素算法：记录下每个节点的父亲，使节点u,v一步一步地向上找父亲，直到找到相同的“祖先”，即是
  所求的答案，时间复杂度O(n)
• 优化算法（倍增法）：利用二进制的思想，想办法使一步一步向上搜索变成以2^k的向上跳。所以
  定义一个f[][]数组，使f[j][i]表示节点i的2^j倍祖先。

算法实现

1.预处理出所有节点的深度和父节点

* BFS防止爆栈 无法处理孩子个数
* DFS可能会爆栈 可以处理孩子个数 使用时建议扩栈

2.处理各节点的所有祖先节点

3.将所查询的两点上升到同一高度

* 找到祖先(以2^k的高度向上找)
* 未找到祖先，同时上升高度至找到公共祖先

---

附加代码

定义及初始化

#pragma comment(linker, "/STACK:10240000000,10240000000")//扩栈，要用c++交，用g++交并没有什么卵用。。。
const int N = 100005;
int n , m , pre[N] , rt[N], mcnt;//pre 邻接表数组  rt 求根节点 mcnt 邻接表下标变量
bool vis[N];
struct edge
{
        int x , next;
} e[N << 1]; //邻接表
int dep[N] , f[17][N] , Lev , s[N];
//dep[]储存深度   1<<16 < N  f[j][i] 表示i的第2^j个祖先 s[]孩子个数
void init()
{
        memset(pre , -1 , sizeof(pre));
        memset(rt, 0, sizeof(rt));
        mcnt = 0;
}

算法函数

void addedge(int x, int y)//邻接表加边函数
{
        e[mcnt].x = y,
        e[mcnt].next = pre[x],
        pre[x] = mcnt ++;
}
void dfs(int x , int fa)///也可以用bfs，但bfs不能统计节点孩子个数
{
        dep[x] = dep[fa] + 1;
        f[0][x] = fa , s[x] = 1;
        for (int i = pre[x] ; i!=-1 ; i = e[i].next)
        {
                int y = e[i].x;
                if (y != fa)
                {
                        dfs(y , x);
                        s[x] += s[y];///节点x的孩子个数
                }
        }
}
//	dfs处理后，要进一步处理得到节点的所有祖先
//	for (j = 1 ; 1 << j < n ; ++ j)
//		for (i = 1 ; i <= n ; ++ i)
//		{
//			f[j][i] = f[j - 1][f[j - 1][i]];
//		}
//	Lev = j - 1;
void bfs(int rt)///不需要求孩子个数，同时防止暴栈
{
        queue<int> q;
        q.push(rt);
        f[0][rt] = 0, dep[rt] = 1, vis[rt] = 1;
        while (!q.empty())
        {
                int fa = q.front();
                q.pop();
                for (int i = pre[fa] ; ~i ; i = e[i].next)
                {
                        int x = e[i].x;
                        if (!vis[x])
                        {
                                dep[x] = dep[fa] + 1;
                                f[0][x] = fa , vis[x] = 1;
                                q.push(x);
                        }
                }
        }
}
int LCA(int x , int y)
{
        if (dep[x] > dep[y])
        {
                swap(x , y);
        }
        for (int i = Lev ; i >= 0 ; -- i)///找y的第dep[y] - dep[x]个祖先
                if (dep[y] - dep[x] >> i & 1)//dep[y]-dep[x]刚好比2的i次方大时
                {
                        y = f[i][y];
                }
        if (x == y)
        {
                return y;
        }
        for (int i = Lev ; i >= 0 ; -- i)//同一高度后开始找祖先
                if (f[i][x] != f[i][y])//不停的上次2的i次方，直到i==0
                {
                        x = f[i][x] , y = f[i][y];
                }
        return f[0][x];
}
int get_kth_anc(int x , int k) ///找x的第k个祖先
{
        for (int i = 0 ; i <= Lev ; ++ i)
                if (k >> i & 1)
                {
                        x = f[i][x];
                }
        return x;
}