（Tarjan的脱机最小公共祖先算法）在一棵有根树T中，两个节点u和v的最小公共祖先(least commom ancestor)w是节点u和v的一个公共祖先，且它有最大的深度。在脱机最小公共祖先问题(off-line least commom ancestors problem)中，给定一棵有根树T和一个在T中的无序节点对的任意集合P={{u,v}}，我们希望确定P中每对的最小公共祖先。
为了解决脱机最小公共祖先问题，下面的过程通过对LCA(T.root)的初始调用，来执行对T的树遍历，假设在执行遍历之前，每个节点被着色为白色。
LCA(u)
1 MAKE-SET(u)
2 FIND-SET(u).ancestor=u
3 for each child v of u inT
4 LCA(v)
5 UNION(u,v)
6 FIND-SET(u).ancestor=u
7 u.color=BLACK
8 if each node v such that {u,v}
P
9 if v.color=BLACK
10 print "The least commom ancestor of "u" and " v "is " FIND-SET(v).ancestor" a.证明：对每对 {u,v}P，第10行恰好只执行一次。
b.证明：在调用LCA(u)时，不相交结合数据结构的集合数等于T中u的深度。
c.证明：对每对 {u,v}P，LCA能正确的输出u和v的最小公共祖先。
d.假设我们使用不相交集合数据结构实现，试分析LCA的运行时间。
