Algorithm Miscellany - Graph Theory

最近为了准备保研的机试，开始看OI-WIKI并且刷题，这个博客主要用来记录我还不熟悉，或者冷门的一些算法和trick技巧

树的中心#

在树中，如果结点$x$作为根结点时，从$x$出发的最长链最短，那么称$x$为这棵树的中心

• 树的中心不一定唯一，但最多有两个，且这两个中心是相邻的
• 树的中心一定位于树的直径上

树的重心#

最近公共祖先#

树链剖分#

构造方式#

树连剖分有多种形式，如重连剖分，长链剖分和用于Link/cut Tree的剖分，大多数情况下，树链剖分都指重链剖分

重链剖分可以将树上的任意一条路径划分成不超过$O(\log n)$条连续的链，每条链上的点深度互不相同。

我们给出一些定义:

定义重子结点表示其子结点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子结点，就无重子结点。定义轻子结点表示剩余的所有子结点，从这个子结点到重子子结点的边叫

常见应用#

路径上维护#

可以通过树链剖分求树上两点路径权值和。链上的DFS序是连续的，可以使用线段树、树状数组维护。每次选择深度较大的链往上跳，直到两点在同一条链上。同样的跳链适用于维护、统计路径上的其他信息

子树维护#

求最近公共祖先#

长链剖分#

同余最短路#