书接上文

树上倍增的具体实现

其实树上倍增大致可以分为三个步骤。

1. dfs 预处理倍增数组设 $dp[x][i]$ 表示 $x$ 点向上跳 $2^i$ 到达的点，初始值 $dp[x][0]$ 的值就为 $x$ 的父亲节点的编号，在从根节点往下遍历的过程中，我们已经得到了该点上方所有点的倍增信息，可以得到状态转移方程：
   $$dp[x][i]=dp[dp[x][i-1][i-1];$$

for (int j = 1; (1 << j) <= deep[x] - 1; j++) {dp[x][j] = dp[dp[x][j - 1]][j - 1];
}

2. 调整两点深度对于深度不同的点，找最近公共祖先比较麻烦，所以我们先把两点的深度统一，即让深度较深的点跳到和深度较浅的点同一深度。具体跳跃方法可以参考差值的二进制数，比如 $(10110{)}_2$ ,就需要向上跳 $2^1,2^2,2^4$。换言之就是，找当前数值中最大的 $2^k$ 的数，找到后再减去这个数，然后继续找。

if (deep[x] < deep[y]) swap(x, y);
int index = __lg(deep[x] - deep[y]);
for (int i = index; i >= 0; i--) {if (deep[dp[x][i]] >= deep[y])x = dp[x][i];if (deep[x] == deep[y])break;
}

3. 找最近公共祖先对于深度相同的两点 $u$ , $v$ ，他们的最近公共祖先可能是任意一个点，那么如何跳跃呢？我们观察这个两个点的 $dp$ 数组可以发现，在 $i$ 比较大的时候, $dp[u][i]=dp[v][i]$ ,说明此时已经跳到了最近公共祖先上方，我们需要找到 $dp[u][i]!=dp[v][i]$
   由于我们也不知道i的具体值，所以只能一个一个尝试，当树的深度最大为 $10^5$ 时，$i$ 的最大值为17即可，$i$ 的值和数据范围 有关，一般不会超过20，如果发现 $dp[u][i]==dp[v][i]$,则不动，否则就同时跳到 $dp[x][i]$ 这个点,由于一个数一定对应一个二进制数，所以最终一定会跳到最近公共祖先。

for (int j = 18; j >= 0; j--) {if (dp[x][j] == dp[y][j]) continue;x = dp[x][j], y = dp[y][j];
}
return dp[x][0];

Tips:
对于边权为1的树，找到两点的最近公共祖先后，通过两点的深度差相减就能得到答案。对于边权不为1的树，虽然也是通过深度差相减得到答案，但是要注意，如果 deep 数组中存储的是该点到根节点的距离，那么在树上倍增第二步操作中，把两个点移动到相同深度的操作就是错误的，这里的深度指的是离根节点经过的节点数量，不是离根节点的距离，所以对于有边权的树，我们需要重新开一个距离数组 dis ，而不能直接修改 deep 数组，这两个在该代码中的作用是不一样的。

小结

树上倍增经常用来求解需要找最近公共祖先的问题，同样，对于序列问题，很多时候还需要求极值，树上倍增也可以用来处理树上路径的极值。处理办法和倍增求区间极值有一点区别，因为对于树上的每一个点，有唯一的父亲节点，但是儿子节点有很多，没有办法记录祖先节点向下找 $2^k$ 这个区间内的答案。
那么如何求解 $u$ 点到最近公共祖先 $x$ 之间的极值呢？先维护一个极值的倍增数组，$max[x][i]$ 表示 $x$ 点到 $x$ 向上移动 $2^i$ 这个区间的极值，在 $u$ 点往上跳的过程中，同时更新极值即可。