树的中心#
在树中，如果结点 作为根结点时，从 出发的最长链最短，那么称 为这棵树的中心。
- 树的中心不一定唯一，但最多有两个，且这两个中心是相邻的
- 树的中心一定位于树的直径上
- 树上所有点到其最远点的路径一定交会于树的中心
- 当树的中心为根节点时，其到达直径端点的两条链分别为最长链和次长链
- 当通过
求法:寻找一个点，使其作为根节点时，最长链的长度最短
- 维护，表示节点子树内的最长链
- 维护，表示不与
// 这份代码默认节点编号从 1 开始，即 1 ∈ [1, n]，使用vector存图
树的重心#
如果在树中删去某个结点后，得到的图中每个连通分量的大小均不超过原树结点数的一半，就称这个结点为整棵树的中心。删去某一结点后得到的最大连通分量的大小也称为该结点的重量。利用这一概念，重心的定义可以叙述为重量不超过树结点数的一半的节点
最近公共祖先#
最近公共祖先简称。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。为了方便，我们记某点集
树链剖分#
构造方式#
树链剖分有多种形式，如重链剖分、长链剖分和用于 Link/Cut Tree 的剖分，大多数情况下，树链剖分都指重链剖分。
重链剖分可以将树上的任意一条路径划分成不超过 条连续的链，每条链上的点深度互不相同。
我们给出一些定义：
定义重子结点表示其子结点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子结点，就无重子结点。定义轻子结点表示剩余的所有子结点，从这个子结点到重子结点的边叫
常见应用#
路径上维护#
可以通过树链剖分求树上两点路径权值和。链上的 DFS 序是连续的，可以使用线段树、树状数组维护。每次选择深度较大的链往上跳，直到两点在同一条链上。同样的跳链适用于维护、统计路径上的其他信息。