树上倍增

• 建立每个节点的深度表、deep 数组
• 建立每个节点往上跳 1、2、4、8 步能达到的节点编号，ST 表
• 给定任意节点 i, 可以快速查询，从 i 节点往上走的路径中位于 s 层的节点编号，单次查询时间复杂度 O(log n)

实际上就是在建立树之后用 dfs 遍历，在统计每个节点对应的深度的同时使用递推公式计算出 ST 表。

最后通过 ST 表的特性向上查找共同根节点就是树上倍增的 lca 应用。

ST 表

ST[i][p]，实际上就是 i 节点向上走 (1 << p) 步所到达的节点。这里给出递推公式

ST[i][p] = ST[ST[i][p-1]][p-1]; // 很容易理解，根据之前节点统计过的结果推出该节点的结果

在 dfs 中，已知 i 节点的父节点全部计算过，所以可以直接使用递推公式。

lca 过程

lca 可以解决树中的最短路径问题。这里使用 ST 表向上查找时，可以很快速的确定两个节点共同的最近父亲节点。

我也不知道咋证明，这里给出查找代码：

int lca(int a, int b) {
    if (dep[a] < dep[b]) {
        int temp = a;
        a = b;
        b = temp;
    }
    for (int p = power; p >= 0; p--) {
        if (dep[stjump[a][p]] >= dep[b]) {
            a = stjump[a][p]; // 这里使要查询的两个节点处于同一深度
        }
    }
    if (a == b)
        return a;

    for (int p = power; p >= 0; p--) {
        if (stjump[a][p] != stjump[b][p]) {
            a = stjump[a][p];
            b = stjump[b][p]; // 使二者的深度与目标深度相差一
        }
    }
    return stjump[a][0];
}

建图

这里推荐的建图方法是链式前向星，其使用三个数组来查找每个节点延伸出去的边。

void add(int u, int v, int w) {
    // u -> v, 权重是w
    next[cnt] = head[u];  // 现在这条边的上一条边是出发点的头部边
    to[cnt] = v;
    weight[cnt] = w;
    head[u] = cnt;  // 出发点的头部边更新为现在的边
    cnt++;
}

// 无向图要add两次

for (int i = 1; i <= n; i++) {                       // i是节点号
    for (int ei = head[i]; ei > 0; ei = next[ei]) {  // ei是边号
    }

把二叉树当成一个有向图来看。

这里使用的是 dfs，根据递归来进行深度的移动，所以不需要使用无向图。