算法合集之分治算法在树的路径问题中的应用.pptx

分治算法在树的路径问题中的应用长沙市雅礼中学 漆子超树的路径问题以路径为询问对象的题目 POJ1741,树中点对统计SPOJ QTREE,FTOUR2,QTREE4Astar2008复赛 黑白树论文内容论文内容一、树的分治算法树的分治的两种常见形式：基于点的分治 基于边的分治二、树的路径剖分算法三、树的分治算法的进一步探讨 如何改进基于边的分治的时间复杂度归纳为基于链的分治一、树的分治算法一、树的分治算法 树的分治算法是分治思想在树型结构上的体现。：除去树中的某些对象，使原树被分解成若干互不相交的部分。两种常见的形式两种常见的形式基于点的分治两种常见的形式两种常见的形式基于点的分治1.选取一个点将无根树转为有根树2.递归处理每一颗以根结点的儿子为根的子树两种常见的形式两种常见的形式基于边的分治两种常见的形式两种常见的形式基于边的分治1.在树中选取一条边2.将原有的树分成两棵不相交的树，递归处理。效率分析效率分析 可以证明在基于点的分治中，如果每次都选取树的重心，那么至多递归 O(LogN)次。基于边的分治最坏情况下递归次数为O(N)。【例一例一】树中点对统计树中点对统计 给定一棵N个结点的带权树。定义dist(u，v)=u，v两点间的路径长度，路径的长度定义为路径上所有边的权和。给定一个K，如果对于不同的两个结点a，b，如果满足dist(a，b)K，则称(a，b)为合法点对。求合法点对个数。N10000,K109一条路径：1.过根节点2.在一颗子树内递归处理树中点对统计树中点对统计记D(i)表示节点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)条重路径。我们称某条路径为重路径，当且仅当它全部由重边组成。那么对于每个点到根的路径上都不超过O(logN)条轻边和条轻边和O(logN)条重路径条重路径。路径剖分算法常用来高效的维护点到根的路径 Spoj的Qtree,Astar2008的黑白树【例二例二】Query On a Tree 给定一棵包含N个结点的树，每个节点要么是黑色，要么是白色。要求模拟两种操作：1)改变某个结点的颜色。2)询问最远的两个黑色结点之间的距离。数据范围：N100000,边权绝对值不超过1000 此题出自2007年浙江省选,但此题中树的边权可能为负，无法使用括号序列。另寻他法另寻他法路径剖分算法路径剖分算法 这道题的算法似乎与路径剖分毫无关系，那么我们是否能用路径剖分算法解决此题呢？路径剖分与树的分治的联系路径剖分与树的分治的联系一棵树及其剖分路径剖分与树的分治的联系路径剖分与树的分治的联系 路径剖分每次删除了一条链，所以路径剖分算法可以看做是基于链的分治基于链的分治 按照点到根结点路径上的轻边个数分层摆放。递归树！Query On a Tree 将路径剖分理解成基于链的分治后，我们可以用类似基于点的分治的方法将路径分类。1.与链有重合部分2.与链没有重合部分递归处理Query On a Tree 12N 我们的目标就是要求出满足与此链的重合部分在1,N的路径的最大长度。我们可以用线段树解决这个问题。Query On a Tree 记D(i)表示第i个结点至子树内某个黑色结点的路径中长度的最大值。Dist(i,j)表示链上的第i个点到第j个点的距离。Query On a Tree 对于线段树中的一个区间L,R,我们需要记录下面三个量：=与此链的重合部分在L,R的路径的最大长度LRLRQuery On a Tree LRLRLR 设区间L,R的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间L,Mid和Mid+1,R。我们可以得到如下转移：Query On a Tree LRLRLR 设区间L,R的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间L,Mid和Mid+1,R。我们可以得到如下转移：Query On a Tree LROptOptLROptLR 设区间L,R的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间L,Mid和Mid+1,R。我们可以得到如下转移：Query On a Tree 注意到Dist(i,j)=Dist(1,j)Dist(1,i)O(1)Query On a Tree 对于边界情况L,L,MaxL=D(L)MaxR=D(L)Opt=D2(i)表示第i个结点至子树内某个黑色结点的路径中长度的次大值。MaxD(L)+D2(L),D(L)黑色D(L)+D2(L)白色问题只剩下如何维护问题只剩下如何维护D D和和D2D2的值的值 Query On a Tree 该点的儿子到某个黑点路径的最大长度链的头结点链的头结点到某个黑点路径的最大长度这正是我们前面已经维护了的量这正是我们前面已经维护了的量MaxL一个点向下至某个黑色结点的路径链的头结点链的头结点Query On a Tree 我们可以使用堆来维护一个点向下至某个黑色结点的路径长度集合O(1)时间复杂度分析时间复杂度分析询问操作：我们使用堆来存贮每条链的最优结果 修改操作：修改一个点最多影响O(logN)条链，对于每条链我们需要修改堆和线段树，O(logN)O(1)O(log2N)路径剖分进一步的分析基于链的分治AC三、树的分治算法的进一步探讨 基于点的分治删除一个点后树的个数太多，加大了设计高效算法的难度基于边的分治删除一条边后仅有两两棵树 最坏的时间复杂度限制了该算法的应用改进!如何改进基于边的分治的时间复杂度改变选择边的方法？X改变树的结构！无论选择哪条边，结果都是一样的 如何改进基于边的分治的时间复杂度 回想上题，题目所关注的对象是两个黑点之间的距离，这就提醒我们可以在不影响树中黑色结点之间的距离的前提下加入白色结点如何改进基于边的分治的时间复杂度 通过对每个结点到其儿子的路径中加入了白色结点，使之成为了类似线段树线段树的结构。叶节点为N的线段树共有2N个结点，所以含有N个结点的树转化后所得的新树最多包含2N个结点。每个点的度至多为3 如何改进基于边的分治的时间复杂度定理：如果一棵包含N个结点的树中每个点的度均不大于D，那么存在一条边，使得分出的两棵子树的结点个数在N/(D+1),N*D/(D+1)。改进后的算法最坏情况下递归深度为 O(LogN)使用基于边的分治解决上题使用基于边的分治解决上题一条路径：1.过中心边2.在一颗子树内1.过中心边过中心边递归处理使用基于边的分治解决上题使用基于边的分治解决上题 记录两个根结点到其子树内某个黑色结点的路径的最大长度 最优路径最优路径修改修改O(logN)询问询问O(1)时间复杂度分析时间复杂度分析询问操作：对每颗树都记录其两个子树的最优值修改操作：一个点最多属于O(logN)棵树，对于每棵树我们需要修改堆，O(logN)O(1)O(log2N)我们达到了与使用路径剖分同阶的时间复杂度。算法更加简单总结总结1.算法的常数：基于链的分治 基于点的分治 N/2，那么我们考虑V作为根结点的情况，记Size(X)表示此时以X为根的子树的结点个数。定理：存在一个点使得分出的子树的结点个数均不大于N/2证明：如图。对于A部分，显然Size(Ti)Size(V)对于B部分，Size(U)=N-Size(V)1时，我们设最优方案为边(U,V)，且以U,V为根的两棵子树的结点个数分别为S和N-S，不妨设SN-S。最优方案指选取一条边使得删除这条边后所分离出来的两棵子树的结点个数较大值最小。设X为U的儿子中以X为根的子树的结点个数最大的一个，我们考虑另一种方案(X,U)。设除去边(X,U)后以X为根的子树结点个数为P，显然P(S-1)/(D-1)，由于PS且边(U,V)是最优方案，所以N-PS，与P(S-1)/(D-1)联立可得S(D-1)N+1)/D，又ND+1，所以SN*D/(D+1)。证毕