国家集训队2009论文集分治算法在树的路径问

IOI2009中国国家集训队论文长沙市雅礼中学漆子超1分治算法在树的路径问题中的应用【摘要】树作为一类特殊的数据结构，在信息学中有着极为重要的作用，各类关于树的题目在竞赛中更是屡见不鲜。本文选取了近几年出现的关于树的路径的题目，并结合例题讲解了分治算法在此类问题上的应用。【关键字】树路径路径剖分分治数据结构IOI2009中国国家集训队论文长沙市雅礼中学漆子超2【目录】【序言】........................................................................................................................3【正文】........................................................................................................................4一.树的分治算法....................................................................................................4基于点的分治：..............................................................................................4基于边的分治：..............................................................................................4效率分析：......................................................................................................5【例1】树中点对统计...................................................................................8算法分析...................................................................................................8【例2】FreeTour2......................................................................................10算法分析.................................................................................................10【本节小结】................................................................................................13二．树的路径剖分算法：...................................................................................14【例3】QueryOnaTree..............................................................................14算法分析.................................................................................................14引入路径剖分.........................................................................................14轻重边路径剖分.....................................................................................15【例4】黑白树...........................................................................................17算法分析.................................................................................................17【小结】........................................................................................................18路径剖分与树的分治的联系：....................................................................19【例5】QueryOnaTreeⅣ........................................................................20算法分析.................................................................................................20【本节小结】................................................................................................23三．树的分治的进一步探讨：...........................................................................24如何改进基于边的分治的时间复杂度........................................................24使用基于边的分治解决【例2】.................................................................26使用基于边的分治解决【例5】.................................................................27四．全文总结.......................................................................................................28【参考文献】..............................................................................................................29【感谢】......................................................................................................................29【附录】......................................................................................................................29IOI2009中国国家集训队论文长沙市雅礼中学漆子超3【序言】树被定义为没有圈的连通图，具有以下几个性质：1.在树中去掉一条边后所得的图是不连通的。2.在树中添加一条边后所得的图一定存在圈。3.树的每一对顶点U和V之间有且仅有一条路径。由于树具有一般图所没有的特点，因此在竞赛中有着更加广泛的应用，尤其是关于树中路径的问题，即一类以路径为询问对象的题目，更是频繁的出现在各种比赛中，每一个有志于OI及ACM的选手都应该掌握这类问题的算法。分治，指的是分而治之，即将一个问题分割成一些规模较小的相互独立的子问题，以便各个击破。我们常见的是在一个线性结构上进行分治，而在本文中我们将会讲解分治算法在树结构上的运用，称之为树的分治算法。分治往往与高效联系在一起，而树的分治正是一种用来解决树的路径问题的高效算法。下面让我们一起来感受树的分治算法的美妙吧。IOI2009中国国家集训队论文长沙市雅礼中学漆子超4【正文】一.树的分治算法下面给出树的分治算法的两个常见形式：基于点的分治：首先选取一个点将无根树转为有根树，再递归处理每一颗以根结点的儿子为根的子树。基于边的分治：在树中选取一条边，将原树分成两棵不相交的树，递归处理。IOI2009中国国家集训队论文长沙市雅礼中学漆子超5效率分析：首先我们考虑如何选取点（边）。对于基于点的分治，我们选取一个点，要求将其删去后，结点最多的树的结点个数最小，这个点被称为“树的重心”。而基于边的分治，我们选取的边要满足所分离出来的两棵子树的结点个数尽量平均，这条边称为“中心边1”。而对于这两个问题，都可以使用在树上的动态规划来解决，时间复杂度均为)(NO，其中N为树的结点总数。对于树的分治算法来说，递归的深度往往决定着算法效率的高低，下面我们来分析上述两种方式的最坏递归深度。定理1：存在一个点使得分出的子树的结点个数均不大于2/N证明：假设U是树的重心，它与VkVV2,1相邻，记)(XSize表示以X为根的子树的结点个数。记V为VkV1中Size值最大的点。我们采取反证法，即假设2/)(NVSize，那么我们考虑如果选取V作为根结点的情况，记)('XSize表示此时以X为根的子树的结点个数。如下图，对于A部分，显然)()('VSizeTiSize，对于B部分，Size(V)N/2Size(V)-N(U)Size'，这与我们假设矛盾。定理得证。1由于作者没有在有关文献中发现这条边的名称，暂且称之为中心边IOI2009中国国家集训队论文长沙市雅礼中学漆子超6由定理1可得，在基于点的分治中每次我们都会将树的结点个数减少一半，因此递归深度最坏是)(logNO的，在树是一条链的时候达到上界。定理2：如果一棵树中每个点的度均不大于D，那么存在一条边使得分出的两棵子树的结点个数在)]1/(*),1/([DDNDN。)2(N证明：不妨令D为所有点的度的最大值。当1D时，命题显然。当1D时，我们设最优方案为边VU，且以VU,为根的两棵子树的结点个数分别为S和SN，不妨设SNS。设X为U的儿子中以X为根的子树的结点个数最大的一个，我们考虑另一种方案UX，设除去边UX后以X为根的子树结点个数为P。显然)1/()1(DSP，由于SP且边VU是最优方案，所以SPN，与)1/()1(DSP联立可得DNDS/)1)1((，又1DN，所以)1/(*DDNS。证毕。IOI2009中国国家集训队论文长沙市雅礼中学漆子超7由定理2我们可以得到在D为常数时，基于边的分治递归最坏深度为)(logNO。但是在一般的题目中，D可能较大甚至达到)(NO，这时这个算法的效率十分低，因此在本节中我们只考虑使用基于点的分治。IOI2009中国国家集训队论文长沙市雅礼中学漆子超8【例1】树中点对统计2给定一棵)100001(NN个结点的带权树，定义),(vudist为vu,两点间的最短路径长度，路径