资源描述：
《Tarjan算法和树上倍增算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Tarjan算法和树上倍增算法LCA（LeastCommonAncestor），顾名思义，是指在一棵树中，距离两个点最近的两者的公共节点。也就是说，在两个点通往根的道路上，肯定会有公共的节点，我们就是要求找到公共的节点中，深度尽量深的点。还可以表示成另一种说法，就是如果把树看成是一个图，这找到这两个点中的最短距离。本文先介绍一个离线的算法，叫做tarjan算法。这个算法是基于并查集和DFS的。Dfs的作用呢，就是递归，一次对树中的每一个节点进行处理。而并查集的作用就是当dfs每访问完（注意，这里是访问完）到一个点的时候，就通过并查集将这个点，和它的子节点链接在
2、一起构成一个集合，也就是将并查集中的pnt值都指向当前节点。这样就把树中的节点分成了若干个的集合，然后就是根据这些集合的情况来对输入数据来进行处理。首先，Tarjan算法是一种离线算法，也就是说，它要首先读入所有的询问（求一次LCA叫做一次询问），然后并不一定按照原来的顺序处理这些询问。而打乱这个顺序正是这个算法的巧妙之处。看完下文，你便会发现，如果偏要按原来的顺序处理询问，Tarjan算法将无法进行。Tarjan算法是利用并查集来实现的。它按DFS的顺序遍历整棵树。对于每个结点x，它进行以下几步操作：*计算当前结点的层号lv[x]，并在并查集中建立仅包含x结
3、点的集合，即root[x]:=x。*依次处理与该结点关联的询问。*递归处理x的所有孩子。*root[x]:=root[father[x]]（对于根结点来说，它的父结点可以任选一个，反正这是最后一步操作了）。现在我们来观察正在处理与x结点关联的询问时并查集的情况。由于一个结点处理完毕后，它就被归到其父结点所在的集合，所以在已经处理过的结点中（包括x本身），x结点本身构成了与x的LCA是x的集合，x结点的父结点及以x的所有已处理的兄弟结点为根的子树构成了与x的LCA是father[x]的集合，x结点的父结点的父结点及以x的父结点的所有已处理的兄弟结点为根的子树构成
4、了与x的LCA是father[father[x]]的集合……（上面这几句话如果看着别扭，就分析一下句子成分，也可参照右面的图）假设有一个询问(x,y)（y是已处理的结点），在并查集中查到y所属集合的根是z，那么z就是x和y的LCA，x到y的路径长度就是lv[x]+lv[y]-lv[z]*2。累加所有经过的路径长度就得到答案。现在还有一个问题：上面提到的询问(x,y)中，y是已处理过的结点。那么，如果y尚未处理怎么办？其实很简单，只要在询问列表中加入两个询问(x,y)、(y,x)，那么就可以保证这两个询问有且仅有一个被处理了（暂时无法处理的那个就pass掉）。而
5、形如(x,x)的询问则根本不必存储。如果在并查集的实现中使用路径压缩等优化措施，一次查询的复杂度将可以认为是常数级的，整个算法也就是线性的了举例说明(非证明):假设遍历完10的孩子,要处理关于10的请求了取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10集合的祖先便是关键路径上距离集合最近的点比如此时:1,2,5,6为一个集合,祖先为1,集合中点和10的LCA为13,7为一个集合,祖先为3,集合中点和10的LCA为38,9,11为一个集合,祖先为8,集合中点和10的LCA为810,12为一个集合,祖先为10,集合中点和10的LCA为10你看,集合
6、的祖先便是LCA吧,所以第3步是正确的道理很简单,LCA(u,v)便是根至u的路径上到节点v最近的点为什么要用祖先而且每次合并集合后都要确保集合的祖先正确呢?因为集合是用并查集实现的,为了提高速度,当然要平衡加路径压缩了,所以合并后谁是根就不确定了,所以要始终保持集合的根的祖先是正确的
