算法合集之《分治算法在树的路径问题中的应用》省公开课金奖全国赛课一等奖微课获奖课件

分治算法在树路径问题中应用长沙市雅礼中学

漆子超1/50树路径问题以路径为问询对象题目POJ1741,树中点对统计SPOJQTREE,FTOUR2,QTREE4Astar复赛黑白树2/50论文内容一、树分治算法树分治两种常见形式：基于点分治基于边分治二、树路径剖分算法三、树分治算法深入探讨怎样改进基于边分治时间复杂度归纳为基于链分治3/50一、树分治算法树分治算法是分治思想在树型结构上表达。：除去树中一些对象，使原树被分解成若干互不相交部分。分4/50两种常见形式基于点分治5/50两种常见形式基于点分治1.选取一个点将无根树转为有根树2.递归处理每一颗以根结点儿子为根子树6/50两种常见形式基于边分治7/50两种常见形式基于边分治1.在树中选取一条边2.将原有树分成两棵不相交树，递归处理。8/50效率分析能够证实在基于点分治中，假如每次都选取树重心，那么至多递归O(LogN)次。…基于边分治最坏情况下递归次数为O(N)。…9/50【例一】树中点对统计给定一棵N个结点带权树。定义dist(u，v)=u，v两点间路径长度，路径长度定义为路径上全部边权和。给定一个K，假如对于不一样两个结点a，b，假如满足dist(a，b)≤K，则称(a，b)为正当点对。求正当点对个数。N≤10000,K≤10910/50一条路径：1.过根节点2.在一颗子树内?递归处理树中点对统计11/50记D(i)表示节点i到根节点路径长度Answer=满足D(i)+D(j)≤K(i,j)个数i,j属于不一样子树O(NlogN)树中点对统计12/50时间复杂度分析每层时间复杂度不超出O(NlogN)最多递归O(logN)次O(Nlog2N)13/50二、路径剖分算法轻重边路径剖分将树中边分为两类：轻边和重边。

记Size(U)表示以U为根子树结点个数。令V为U儿子中Size(V)最大一个，那么我们称边(U，V)为重边，其余边为轻边。14/50轻重边路径剖分我们称某条路径为重路径，当且仅当它全部由重边组成。那么对于每个点到根路径上都不超出O(logN)条轻边和O(logN)条重路径。我们称某条路径为重路径，当且仅当它全部由重边组成。那么对于每个点到根路径上都不超出O(logN)条轻边和O(logN)条重路径。路径剖分算法惯用来高效维护点到根路径SpojQtree,Astar黑白树…15/50【例二】QueryOnaTreeⅣ给定一棵包含N个结点树，每个节点要么是黑色，要么是白色。要求模拟两种操作：1)改变某个结点颜色。2)问询最远两个黑色结点之间距离。数据范围：N≤100000,边权绝对值不超出1000此题出自年浙江省选,但此题中树边权可能为负，无法使用括号序列。另寻他法16/50路径剖分算法这道题算法似乎与路径剖分毫无关系，那么我们是否能用路径剖分算法处理此题呢？17/50路径剖分与树分治联络一棵树及其剖分18/50路径剖分与树分治联络路径剖分每次删除了一条链，所以路径剖分算法能够看做是基于链分治

按照点到根结点路径上轻边个数分层摆放。递归树！19/50QueryOnaTreeⅣ将路径剖分了解成基于链分治后，我们能够用类似基于点分治方法将路径分类。1.与链有重合部分2.与链没有重合部分递归处理20/50QueryOnaTreeⅣ…12N我们目标就是要求出满足与此链重合部分在[1,N]路径最大长度。我们能够用线段树处理这个问题。21/50QueryOnaTreeⅣ记D(i)表示第i个结点至子树内某个黑色结点路径中长度最大值。Dist(i,j)表示链上第i个点到第j个点距离。22/50QueryOnaTreeⅣ对于线段树中一个区间[L,R],我们需要统计下面三个量：=与此链重合部分在[L,R]路径最大长度LRLR23/50QueryOnaTreeⅣLRLRLR

设区间[L,R]结点编号为P，Lc,Rc分别表示P左右两个儿子，区间[L,Mid]和[Mid+1,R]。我们能够得到以下转移：24/50QueryOnaTreeⅣLRLRLR

设区间[L,R]结点编号为P，Lc,Rc分别表示P左右两个儿子，区间[L,Mid]和[Mid+1,R]。我们能够得到以下转移：25/50QueryOnaTreeⅣLROptOptLROptLR

设区间[L,R]结点编号为P，Lc,Rc分别表示P左右两个儿子，区间[L,Mid]和[Mid+1,R]。我们能够得到以下转移：26/50QueryOnaTreeⅣ注意到Dist(i,j)=Dist(1,j)–Dist(1,i)O(1)27/50QueryOnaTreeⅣ对于边界情况[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值28/50QueryOnaTreeⅣ…该点儿子到某个黑点路径最大长度链头结点到某个黑点路径最大长度！这正是我们前面已经维护了量MaxL一个点向下至某个黑色结点路径链头结点29/50QueryOnaTreeⅣ我们能够使用堆来维护一个点向下至某个黑色结点路径长度集合O(1)30/50时间复杂度分析问询操作：我们使用堆来存贮每条链最优结果修改操作：修改一个点最多影响O(logN)条链，对于每条链我们需要修改堆和线段树，O(logN)O(1)O(log2N)路径剖分深入分析基于链分治AC31/50三、树分治算法深入探讨基于点分治删除一个点后树个数太多，加大了设计高效算法难度基于边分治删除一条边后仅有两棵树最坏时间复杂度限制了该算法应用改进!32/50怎样改进基于边分治时间复杂度…改变选择边方法？X改变树结构！不论选择哪条边，结果都是一样33/50怎样改进基于边分治时间复杂度回想上题，题目所关注对象是两个黑点之间距离，这就提醒我们能够在不影响树中黑色结点之间距离前提下加入白色结点34/50怎样改进基于边分治时间复杂度经过对每个结点到其儿子路径中加入了白色结点，使之成为了类似线段树结构。叶节点为N线段树共有2N个结点，所以含有N个结点树转化后所得新树最多包含2N个结点。每个点度至多为335/50怎样改进基于边分治时间复杂度定理：假如一棵包含N个结点树中每个点度均小于D，那么存在一条边，使得分出两棵子树结点个数在[N/(D+1),N*D/(D+1)]。改进后算法最坏情况下递归深度为

O(LogN)36/50使用基于边分治处理上题一条路径：1.过中心边2.在一颗子树内1.过中心边递归处理37/50使用基于边分治处理上题统计两个根结点到其子树内某个黑色结点路径最大长度最优路径修改O(logN)问询O(1)38/50时间复杂度分析问询操作：对每颗树都统计其两个子树最优值修改操作：一个点最多属于O(logN)棵树，对于每棵树我们需要修改堆，O(logN)O(1)O(log2N)我们到达了与使用路径剖分同阶时间复杂度。算法愈加简单39/50总结1.算法常数：基于链分治<基于点分治<基于边分治2.基于链分治能够用来维护路径上点(边)。假如维护对象是路径长度，基于点(边)分治算法能力更强。这几个算法各有所长，需要我们依据详细情况，灵活利用，以最正确方式处理题目。3.与基于点分治比较，基于边分治在设计高效算法思索难度上显著小于前者。40/50谢谢大家41/50算法常数1.在路径剖分算法中，链长度和链个数是相互制约，所以路径剖分算法在实际运行中是很快。2.为了改进基于边分治最坏复杂度，我们将一个结点个数为N树改造成了一个结点个数为2N新树，自然增加了常数。42/50算法常数测试环境：Intel®Core™2DuoT72502.00GHz,1GB编译器：VisualC++,Release模式基于链分治基于点分治基于边分治未改进基于边分治N=100000M=1000001.17s1.78s2.28s2.13sN=100000M=5000002.35s3.80s5.79s5.73s43/50算法常数测试环境：Intel®Core™2DuoT72502.00GHz,1GB编译器：VisualC++,Release模式FreePascal2.1.4hide6.inhide7.inhide8.inhide9.in基于链分治0.26s0.59s1.13s1.90s线段树0.21s0.45s1.10s2.35s44/50树重心我们选取一个点，要求将其删去后，结点最多树结点个数最小，这个点被称作”树重心”。45/50

定理：存在一个点使得分出子树结点个数均小于N/2假设U是树重心，记Size(X)表示以X为根子树结点个数。记V为U儿子中Size值最大点。证实：46/50

定理：存在一个点使得分出子树结点个数均小于N/2证实：

假设Size(V)>N/2，那么我们考虑V作为根结点情况，记Size’(X)表示此时以X为根子树结点个数。47/50

定理：存在一个点使得分出子树结点个数均小于N/2证实：如图。对于A部分，显然Size’(Ti)<Size(V)对于B部分，Size’(U)=N-Size(V)<Size(V)这与树重心定义矛盾。定理得证。48/50定理：假如一棵包含N个结点树中每个点度均小于D，那么存在一条边，使得分出两棵子树结点个数在[N/(D+1),N*D/(D+1)]。证实：

不妨令D为全部点度最大值。

当D=1时，命题显然。当D>1时，我们设最优方案为边(U,V)，且以U,V为根两棵子树结点个数分别为S和N-S