笔记汇总

算法分为 预处理 和 在线处理 两部分。

运用了 倍增 的思想，

由于我们 所到的点 的各个决策都是不同的，可以将 不同的点 看作 不同的层。

由倍增可知，每一层有 $log(n)$ 个决策。

如果可以 $O(1)$ 转化不同的决策（未必是同层转化），就可以解决了。

int depth[N], fa[N][17];    // 数据在 2^17 以内

void bfs()
{
    queue<int> q;
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0;
    depth[1] = 1; // 每个点所在的树的深度

    q.push(1);
    while (q.size())            // 由上往下更新，可以确定边界
    {
        int t = q.front();
        q.pop();
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)    // 因为加的是无向边，但只能更新子节点
            {
                depth[j] = depth[t] + 1;    // 更新深度，以便于继续更新之后的节点。
                fa[j][0] = t;               // 往上走 1 步，为父节点，初始化
                q.push(j);                  // 由上往下，继续更新其子节点
                for (int k = 1; k <= 16; k ++ ) // 当前层的所有决策
                    fa[j][k] = fa[fa[j][k - 1]][k - 1]; // 由之前层来更新，存的是能到哪个点
            }
        }
    }
}

然后就是在两个不同层根据不同的转移到达 $LCA$ 点，

如果分别枚举决策，由乘法原理可知，会有 $17!^2$ 种不同决策，

但我们有树的深度，这个限制条件，所以剪去大于条件者，并逐渐收敛，至 $17^2$ 种不同决策，

通常取用一个点代跑来判断，

$LCA$ 点的深度肯定是一样的，要是两个层深度一样，则转移的步数相同，

可以减少到 $17$ 种决策。

所以我们只需要将一个层深度执到与另一层深度相同时所在的点（由上分析知，只有 $17$ 种决策）

注意，我们判断等于时，只能靠决策给出的点，但我们只有小于的信息，

所以，暂取到等于减一，即可，

int lca(int x, int y)
{
    // 确保 x 更深
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 16; k >= 0; k -- )
        if (depth[fa[x][k]] >= depth[y])
        {
            x = fa[x][k];
        }
    if (x == y) return y;
    for (int k = 16; k >= 0; k -- )
        if (fa[x][k] != fa[y][k])   // 为了便于判断等于的条件，如此做所在点不同，最终为等于减一
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0]; // 返回此时 x 的父节点，等于减一加一 = 等于
}