主要考察点分为五个部分：倍增、最短路、最小生成树、数论和组合数学。
倍增
倍增，就是成倍增长。在线性递推超时的时候，我们可以只获取在 k 的整数次幂位置上的值。当需要其他位置上的值时，我们通过 '任意整数可以被分为若干个 k 的次幂项的和' 这一性质，使用获取过的值来得到想要求到的值。 倍增有三大应用场面，分别是 快速幂、LCA、RMQ，快速幂不常考。
倍增 LCA
LCA（Lowest Common Ancestor)为树上算法，意为 最近公共祖先。定义：若干个点的公共祖先中离根 最远 的点就叫这些点的最近公共祖先。
例如下图中，4 和 6 的最近公共祖先是 2；2、4、6 的最近公共祖先是 2。
在 LCA 中，我们可以用 p[x][i] 表示 x 的第 2^i 个祖先，p[x][0] 就是 x 的父亲，p[x][i] 就是 x 的第 2^{i-1} 个祖先的第 2^{i-1} 个祖先。
同时我们维护数组 dep，dep[i] 表示 i 离根的距离。
我们可以通过 dfs 求出 p 数组和 dep 数组。
先给出 预处理 的 dfs 代码：
void dfs(int now, int fa) {
dep[now] = dep[fa] + 1;
p[now][0] = fa;
for (int i = 1; i <= 20; ++i) p[now][i] = p[p[now][i-1]][i-1]; // i=[1,20]，核心
for(auto node : edge[now]) if(node != fa) dfs(node, now);
}
现在我们着重考虑 2 个点的 LCA。首先，我们检查 dep_x >= dep_y，若不满足，则交换 x, y。接着，我们让 x 通过跳跃到达 y 的所在层数。这时，如果我们发现 x == y，则直接返回 x；否则两个点同时往上跳跃，直到 p[x][0] = p[y][0]，最后返回 p[x][0] 即可。
LCA 函数：