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

分治算法在树的路径问题中的应用长沙市雅礼中学漆子超树的路径问题以路径为询问对象的题目POJ1741,树中点对统计SPOJQTREE,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)为合法点对。求合法点对个数。N≤10000,K≤109一条路径：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的黑白树…【例二】QueryOnaTreeⅣ给定一棵包含N个结点的树，每个节点要么是黑色，要么是白色。要求模拟两种操作：1)改变某个结点的颜色。2)询问最远的两个黑色结点之间的距离。数据范围：N≤100000,边权绝对值不超过1000此题出自2007年浙江省选,但此题中树的边权可能为负，无法使用括号序列。路径剖分算法这道题的算法似乎与路径剖分毫无关系，那么我们是否能用路径剖分算法解决此题呢？路径剖分与树的分治的联系一棵树及其剖分路径剖分与树的分治的联系路径剖分每次删除了一条链，所以路径剖分算法可以看做是基于链的分治按照点到根结点路径上的轻边个数分层摆放。QueryOnaTreeⅣ将路径剖分理解成基于链的分治后，我们可以用类似基于点的分治的方法将路径分类。1.与链有重合部分2.与链没有重合部分递归处理QueryOnaTreeⅣ…12N我们的目标就是要求出满足与此链的重合部分在[1,N]的路径的最大长度。我们可以用线段树解决这个问题。QueryOnaTreeⅣ记D(i)表示第i个结点至子树内某个黑色结点的路径中长度的最大值。Dist(i,j)表示链上的第i个点到第j个点的距离。QueryOnaTreeⅣ对于线段树中的一个区间[L,R],我们需要记录下面三个量：)}(),({iDiLDistMaxMaxL)},()({RiDistiDMaxMaxR=与此链的重合部分在[L,R]的路径的最大长度OptLRLRQueryOnaTreeⅣ)}()1,(),({)(RcMaxLMidLDistLcMaxLMaxPMaxLLRLRLR设区间[L,R]的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间[L,Mid]和[Mid+1,R]。我们可以得到如下转移：QueryOnaTreeⅣLRLRLR)},()(),({)(RMidDistLcMaxRRcMaxRMaxPMaxR设区间[L,R]的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间[L,Mid]和[Mid+1,R]。我们可以得到如下转移：QueryOnaTreeⅣ})1,()()(),(),({)(MidMidDistRcMaxLLcMaxRRcOptLcOptMaxPOptLROptOptLROptLR设区间[L,R]的结点编号为P，Lc,Rc分别表示P的左右两个儿子，区间[L,Mid]和[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的值QueryOnaTreeⅣ…该点的儿子到某个黑点路径的最大长度链的头结点到某个黑点路径的最大长度这正是我们前面已经维护了的量MaxL一个点向下至某个黑色结点的路径链的头结点QueryOnaTreeⅣ我们可以使用堆来维护一个点向下至某个黑色结点的路径长度集合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.算法的常数：基于链的分治基于点的分治基于边的分治2.基于链的分治可以用来维护路径上的点(边)。如果维护的对象是路径的长度，基于点(边)的分治算法的能力更强。这几个算法各有所长，需要我们根据具体情况，灵活运用，以最佳的方式解决题目。3.与基于点的分治比较，基于边的分治在设计高效算法的思考难度上明显小于前者。算法的常数1.在路径剖分算法中，链的长度和链的个数是相互制约的，因此路径剖分算法在实际运行中是很快的。2.为了改进基于边的分治的最坏复杂度，我们将一个结点个数为N的树改造成了一个结点个数为2N的新树，自然增加了常数。算法的常数测试环境：Intel®Core™2DuoT72502.00GHz,1GB编译器：VisualC++2008,Release模式基于链的分治基于点的分治基于边的分治未改进的基于边的分治N=100000M=1000001.17s1.78s2.28s2.13sN=100000M=5000002.35s3.80s5.79s5.73s算法的常数测试环境：Intel®Core™2DuoT72502.00GHz,1GB编译器：VisualC++2008,Release模式FreePascal2.1.4hide6.inhide7.inhide8.inhide9.in基于链的分治0.26s0.59s1.13s1.90s线段树0.21s0.45s1.10s2.35s树的重心我们选取一个点，要求将其删去后，结点最多的树的结点个数最小，这个点被称作”树的重心”。定理：存在一个点使得分出的子树的结点个数均不大于N/2假设U是树的重心，记Size(X)表示以X为根的子树的结点个数。记V为U的儿子中Size值最大的点。证明：定理：存在一个点使得分出的子树的结点个数均不大于N/2证明：假设Size(V)N/2，那么我们考虑V作为根结点的情况，记Size’(X)表示此时以X为根的子树的结点个数。定理：存在一个点使得分出的子树的结点个数均不大于N/2证明：如图。对于A部分，显然Size’(Ti)Size(V)对于B部分，Size’(U)=N-Size(V)Size(V)这与树的重心定义矛盾。定理得证。定理：如果一棵包含N个结点的树中每个点的度均不大于D，那么存在一条边，使得分出的两棵子树的结点个数在[N/(D+1),N*D/(D+1)]。证明：不妨令D为所有点的度的最大值。当D=1时，命题显然。当D1时，我们设最优方案为边(U,V)，且以U,V为根的两棵子树的结点个数分别为S和N-S，不妨设S≥N-S。最优方案指选取一条边使得删除这条边后所分离出来的两棵子树的结点个数较大值最小。设X为U的儿子中以X为根的子树的结点个数最大的一个，我们考虑另一种方案(X,U)。设除去边(X,U)后以X为根的子树结点个数为P，显然P≥(S-1)/(D-1)，由于PS且边(U,V)是最优方案，所以N-P≥S，与P≥(S-1)/(D-1)联立可得S≤((D-1)N+1)/D，又N≥D+1，所以S≤N*D/(D+1)。证毕