拓展知识：树

已知二叉树的前序遍历与后序遍历，求可能的树的种数。

最近公共祖先（LCA）

希望快速查询树中某两个结点的最近公共祖先。

实际上，只有两种情况，（1）LCA异于此二结点，此二结点分别处于LCA某两孩子的子树中，（2）其中一个结点是另一个结点的祖先，故LCA为此节点。

预处理各结点的深度\(depth\)与祖先\(fa\)，此处有倍增优化：

记\(ST_{i,j}\)表示\(i\)向上\(2^j\)重祖先，记\(ST_{i,0}=fa_i\)，转移方程为：\(ST_{i,j}=ST_{ST_{i,j-1},j-1}\)

查询阶段：将较深的结点作为主操作数，此处记为\(i\)，在\(depth_i\ge depth_j\)的前提下，使用倍增往上跳，当二者深度相同时，若指向同一结点，返回此结点即可，否则，二者在\(fa_i\neq fa_j\)前提下一齐往上跳，最终返回\(fa_i\)