LCA: Lowest common ancestor 最近公共祖先

倍增求 LCA

预处理向上跳 $2^k$ 步的结果数组 f[k][x]。

求的时候先把两个点跳到一个深度。这里有一个特判，如果重合直接返回这个点。

然后log值从大往小枚举，两个点一起不断向上跳，直至父亲相同，直接返回父节点。

可以 $O(n)$ 预处理log值，把单次查询复杂度降到 $O(常数)$。

复杂度：预处理 $O(n \log n)$，查询 $O(1)$

前置概念

时间戳：搜索时第几个搜索到这个点。如搜索顺序是1->2->3->6，则6的时间戳为4

对于无向图

连通分量：对于图G来的一个子图中，任意两个点都可以彼此到达，这个子图就被称为图G的连通分量（一个点就是最小的连通分量）

最大连通分量：对于图G的一个子图，这个子图为图G的连通分量，且是图G所有连通分量中包含节点数最多的那个，即为G的最大联通分量

DFS

搜索和DP不分家，几乎所有的DP都能用搜索解决（虽然复杂度可能较劣）。不过，如果实在想不出正解，DFS不失为骗分的好手段。

主要的搜索算法有：

1. DFS/BFS爆搜
2. 双向BFS
3. 启发式搜索（又称A*）
4. 迭代加深搜索
5. IDA*（迭代加深+启发式）
6. 记忆化搜索
7. 剪枝

重要程度：1,7,6 > 4,3 > 5,2。

图论算法一般都是揉在一起的，很难单独把算法拆开讲，所以直接上题目吧。分类是大致分的，其实有很多是交叉的。

二叉树

二叉树的遍历有三种，分别为前序遍历，中序遍历和后序遍历，并且给定其中的两种遍历能够求出另一种遍历 (必须已知中序遍历)。