书接上文
树上倍增的具体实现
其实树上倍增大致可以分为三个步骤。
- dfs 预处理倍增数组设
d
p
[
x
]
[
i
]
dp[x][i]
dp[x][i] 表示
x
x
x 点向上跳
2
i
2^i
2i 到达的点，初始值
d
p
[
x
]
[
0
]
dp[x][0]
dp[x][0] 的值就为
x
x
x 的父亲节点的编号，在从根节点往下遍历的过程中，我们已经得到了该点上方所有点的倍增信息，可以得到状态转移方程：
d p [ x ] [ i ] = d p [ d p [ x ] [ i − 1 ] [ i − 1 ] ; dp[x][i]=dp[dp[x][i-1][i-1]; 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];
}
- 调整两点深度对于深度不同的点，找最近公共祖先比较麻烦，所以我们先把两点的深度统一，即让深度较深的点跳到和深度较浅的点同一深度。具体跳跃方法可以参考差值的二进制数，比如 ( 10110 ) 2 (10110)_2 (10110)2 ,就需要向上跳 2 1 , 2 2 , 2 4 2^1,2^2,2^4 21,22,24。换言之就是，找当前数值中最大的 2 k 2^k 2k 的数，找到后再减去这个数，然后继续找。
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;
}
- 找最近公共祖先对于深度相同的两点
u
u
u ,
v
v
v ，他们的最近公共祖先可能是任意一个点，那么如何跳跃呢？我们观察这个两个点的
d
p
dp
dp 数组可以发现，在
i
i
i 比较大的时候,
d
p
[
u
]
[
i
]
=
d
p
[
v
]
[
i
]
dp[u][i]=dp[v][i]
dp[u][i]=dp[v][i] ,说明此时已经跳到了最近公共祖先上方，我们需要找到
d
p
[
u
]
[
i
]
!
=
d
p
[
v
]
[
i
]
dp[u][i]!=dp[v][i]
dp[u][i]!=dp[v][i]
由于我们也不知道i的具体值，所以只能一个一个尝试，当树的深度最大为 1 0 5 10^5 105 时， i i i 的最大值为17即可， i i i 的值和数据范围 有关，一般不会超过20，如果发现 d p [ u ] [ i ] = = d p [ v ] [ i ] dp[u][i]==dp[v][i] dp[u][i]==dp[v][i],则不动，否则就同时跳到 d p [ x ] [ i ] dp[x][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
2^k
2k 这个区间内的答案。
那么如何求解
u
u
u 点到最近公共祖先
x
x
x 之间的极值呢？先维护一个极值的倍增数组，
m
a
x
[
x
]
[
i
]
max[x][i]
max[x][i] 表示
x
x
x 点到
x
x
x 向上移动
2
i
2^i
2i 这个区间的极值，在
u
u
u 点往上跳的过程中，同时更新极值即可。