资源描述：
《算法合集之《分治算法在树的路径问题中的应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、分治算法在树的路径问题中的应用长沙市雅礼中学漆子超树的路径问题以路径为询问对象的题目POJ1741,树中点对统计SPOJQTREE,FTOUR2,QTREE4Astar2008复赛黑白树论文内容一、树的分治算法树的分治的两种常见形式：基于点的分治基于边的分治二、树的路径剖分算法三、树的分治算法的进一步探讨如何改进基于边的分治的时间复杂度归纳为基于链的分治一、树的分治算法树的分治算法是分治思想在树型结构上的体现。：除去树中的某些对象，使原树被分解成若干互不相交的部分。两种常见的形式基于点的分治两种常见的形式基于点的分治1.选取一个点将无根树转为有根树2.递归处理每一颗以根结点的儿子为根的子树
2、两种常见的形式基于边的分治两种常见的形式基于边的分治1.在树中选取一条边2.将原有的树分成两棵不相交的树，递归处理。效率分析可以证明在基于点的分治中，如果每次都选取树的重心，那么至多递归O(LogN)次。…基于边的分治最坏情况下递归次数为O(N)。…【例一】树中点对统计给定一棵N个结点的带权树。定义dist(u，v)=u，v两点间的路径长度，路径的长度定义为路径上所有边的权和。给定一个K，如果对于不同的两个结点a，b，如果满足dist(a，b)≤K，则称(a，b)为合法点对。求合法点对个数。N≤10000,K≤109一条路径：1.过根节点2.在一颗子树内递归处理树中点对统计记D(i)表示节
3、点i到根节点路径的长度Answer=满足D(i)+D(j)≤K的(i,j)个数i,j属于不同的子树O(NlogN)树中点对统计时间复杂度分析每层的时间复杂度不超过O(NlogN)最多递归O(logN)次O(Nlog2N)二、路径剖分算法轻重边路径剖分将树中的边分为两类：轻边和重边。记Size(U)表示以U为根的子树的结点个数。令V为U的儿子中Size(V)最大的一个，那么我们称边(U，V)为重边，其余边为轻边。轻重边路径剖分我们称某条路径为重路径，当且仅当它全部由重边组成。那么对于每个点到根的路径上都不超过O(logN)条轻边和O(logN)条重路径。我们称某条路径为重路径，当且仅当它全部
4、由重边组成。那么对于每个点到根的路径上都不超过O(logN)条轻边和O(logN)条重路径。路径剖分算法常用来高效的维护点到根的路径Spoj的Qtree,Astar2008的黑白树…【例二】QueryOnaTreeⅣ给定一棵包含N个结点的树，每个节点要么是黑色，要么是白色。要求模拟两种操作：1)改变某个结点的颜色。2)询问最远的两个黑色结点之间的距离。数据范围：N≤100000,边权绝对值不超过1000此题出自2007年浙江省选,但此题中树的边权可能为负，无法使用括号序列。另寻他法路径剖分算法这道题的算法似乎与路径剖分毫无关系，那么我们是否能用路径剖分算法解决此题呢？路径剖分与树的分治的联
5、系一棵树及其剖分路径剖分与树的分治的联系路径剖分每次删除了一条链，所以路径剖分算法可以看做是基于链的分治按照点到根结点路径上的轻边个数分层摆放。递归树！QueryOnaTreeⅣ将路径剖分理解成基于链的分治后，我们可以用类似基于点的分治的方法将路径分类。1.与链有重合部分2.与链没有重合部分递归处理QueryOnaTreeⅣ…12N我们的目标就是要求出满足与此链的重合部分在[1,N]的路径的最大长度。我们可以用线段树解决这个问题。QueryOnaTreeⅣ记D(i)表示第i个结点至子树内某个黑色结点的路径中长度的最大值。Dist(i,j)表示链上的第i个点到第j个点的距离。QueryOna
6、TreeⅣ对于线段树中的一个区间[L,R],我们需要记录下面三个量：=与此链的重合部分在[L,R]的路径的最大长度LRLRQueryOnaTreeⅣLRLRLR设区间[L,R]的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间[L,Mid]和[Mid+1,R]。我们可以得到如下转移：QueryOnaTreeⅣLRLRLR设区间[L,R]的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间[L,Mid]和[Mid+1,R]。我们可以得到如下转移：QueryOnaTreeⅣLROptOptLROptLR设区间[L,R]的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间[L,Mi
7、d]和[Mid+1,R]。我们可以得到如下转移：QueryOnaTreeⅣ注意到Dist(i,j)=Dist(1,j)–Dist(1,i)O(1)QueryOnaTreeⅣ对于边界情况[L,L],MaxL=D(L)MaxR=D(L)Opt=D2(i)表示第i个结点至子树内某个黑色结点的路径中长度的次大值。Max{D(L)+D2(L),D(L)}黑色D(L)+D2(L)白色问题只剩下如何维护D和D2的值QueryOnaTr
