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