在竞赛当中，解决 LCA 问题有几大方法：倍增，Tarjan，树剖，欧拉序。其中大部分教练推荐的都会是倍增求 LCA 的方法。但在我和 ljt 的讨论下，树链剖分是更加好的求 LCA 的方式。这并不是完全看我们的好恶，首先，倍增是比较容易写挂掉的（尤其是处理直接父亲之类的边界的时候，很容易 RE 或者 WA），而树链剖分只需要进行两次 dfs，即可在的复杂度下求出 LCA（请注意，这里我用的是算法复杂度上界符号，事实上在实际情况下，链的剖分可能比较少，从而导致复杂度远低于，而且树剖的常数更小，详情请见算法复杂度分析一文）；其次，树链剖分更加通用，我们可以利用轻重链剖分解决树上的很多动态问题，甚至拓展一下便是 LCT。所以我就讲一讲树链剖分。
在编译器开发的优化当中，Lengauer-Tarjan 算法作为求解支配树的高效算法被广泛使用。该算法也在 NOI 大纲的 NOI 级内容当中，而且能够解决一些倍增 LCA 的题（如 ZJOI2012 灾难）。此处就大概介绍一下这个算法。
本文将分为如下几个部分：术语，算法证明，算法内容，Notes（注释），Reference（引用），后记。
以下内容主要来自 Thomas Lengauer 和 Robert Endre Tarjan 的论文以及虎书（现代编译原理），一部分是直接翻译，有的我加上了一些个人理解。以下内容如果来自参考文献的会加上对应的无方括号的角标。有的地方我会给出注释放在 Notes 当中，右上角会加上带有方括号的角标。
生活中我们会遇到很多问题：比如张三和李四认识但是和王五不一定认识；滨和路到龙翔桥可以直接通地铁，但滨和路到萧山国际机场却要换乘。这些问题似乎都有些共性：如果我们把人，地铁站这些对象看成点；把人际关系，地铁线路看成边，从而将这些点连起来，我们可以通过这一幅图中观察出一些性质。其中，这个图形就叫做图（Graph），研究这个性质的理论就叫做图论（Graph Theory）。
严格的讲，图的一般数学定义是一个三元组，其中和是两个不相交的集合，非空，是到的一个映射，、、分别被称为图的顶点集、边集、关联函数。当然，这样表示过于复杂，我们往往会使用一个二元组来表示一个图，将关联函数融入边集中（关联函数这种表达方式此处不讲，到讲有限自动机的时候会再讲讲这个东西）。
