树上搜索.pdf 上课讲义

这份资源是由宁波市镇海中学的符水波老师提供的关于树论的基本概念及相关定义的讲义。树论是图论的一个分支，专注于研究树这种特殊类型的图。在信息学竞赛中，树论问题通常涉及利用树的性质，如直径、重心、最近公共祖先、DFS序等，通过树形动态规划、树上差分、树链剖分以及分治等算法技巧来解决问题。 讲义首先定义了树：一个包含n个节点的无环联通图，其中n个节点的树具有n-1条边。接着，讲义介绍了有根树的概念，包括根、父亲（par）、孩子（son）、祖先、后代等术语。同时，也解释了子树、叶、分支节点、深度、层、高度以及最近公共祖先（LCA）等概念。 在存储方面，讲义提到了两种方法：一是将树作为图的一种特殊类型进行存储，二是对于有根树，可以为每个节点存储其父亲或孩子。在实际应用中，可以根据具体情况选择适当的存储方法。 此外，讲义还讨论了无根树、森林、二叉树、完全二叉树、满二叉树等概念，并指出了动态分配内存的STL容器如vector在时间限制较紧的问题中可能导致超时的现象。 最后，讲义通过一系列的问题和解答，深入探讨了树的直径、树形动态规划、DFS序、树上差分、树链剖分、LCA等算法的应用，以及如何