分治算法在树的路径问题中的应用

国国家集训队论文 长沙市雅礼中学 漆子超 1 分治算法 在 树的路径问题 中 的应用 【摘要】 树作为一类特殊的数据结构，在信息学中有着极为重要的作用，各类关于树的题目在竞赛中更是屡 见不鲜。本文选取了近几年出现的关于树的路径的题目，并结合例题 讲解了分治算法在此类问题上的 应用 。 【关键字】 树 路径 路径剖分 分治 数据结构 国国家集训队论文 长沙市雅礼中学 漆子超 2 【目录】 【序言】 3 【正文】 4 一 . 4 基于点的分治： 4 基 于边的分治： 4 效率分析： 5 【例 1】树中点对统计 . 8 算法分析 . 8 【例 2】 10 算法分析 . 10 【本节小结】 13 二．树的路径剖分算法： . 14 【例 3】 n a . 14 算法分析 . 14 引入路径剖分 . 14 轻重边 路径剖分 . 15 【例 4】黑白树 . 17 算法分析