树的重心和直径(centroid&diameter of a tree)

组别：提高级
难度：6

树的重心也称为质点，如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

重心的特点：

• 树的重心如果不唯一，则至多有两个，且这两个重心相邻。
• 以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
• 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
• 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
• 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

树的直径是树中任意两个节点之间最长路径的长度。这个路径上的节点数目减去一就是树的直径。

显然，一棵树可以有多条直径，他们的长度相等。可以用两次 DFS 或者树形 DP 的方法在 O(n) 时间求出树的直径。

性质：若树上所有边边权均为正，则树的所有直径中点重合。

DFS序（Depth-First Search Order）是指在深度优先搜索（DFS）过程中，访问节点的顺序。DFS是一种遍历或搜索树或图的算法，它尽可能深地搜索树的分支。在遍历过程中，每个节点会被访问一次，并且会记录下访问的顺序，这就是DFS序。

欧拉序（Euler Tour or Eulerian Tour）是在图论中指从一个节点出发，遍历图中所有的边恰好一次，并返回到起点的路径。对于树结构而言，欧拉序是通过深度优先搜索（DFS）遍历树并记录每个节点进出时间的序列。