wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共3篇）

树的重心

定义树的重心是指树上的某个节点，满足删除当前点之后，生成的树的大小的最大值最小。性质性质1 以树的重心为根，那么根节点的每棵子树的大小都小于等于\(\frac{n}{2}\)。性质2 每棵子树的大小都小于等于\(\frac{n}{2}\)的点一定是这棵树的重心。即性质\(1\)的...

树的重心学习笔记

2019-01-29

0 602

树的重心

定义树的重心是指树上的某个节点，满足删除当前点之后，生成的树的大小的最大值最小。性质性质1 以树的重心为根，那么根节点的每棵子树的大小都小于等于\(\frac{n}{2}\)。性质2 每棵子树的大小都小于等于\(\frac{n}{2}\)的点一定是这棵树的重心。即性质\(1\)的...

树的重心学习笔记

2019-01-29

0 485

树的直径

定义树的直径就是指树上的最长路径。一棵树可能有多个直径，并且这些直径一定两两相交。性质性质1 从树上的任何一个点为起点，所找到的最长路径的的终点一定是直径的一个端点。证明: 考虑反证法。 ①假设直径与最长路径没有交集用\(dist(x,y)\)表示从\(x\)到\(y\)...

树的直径学习笔记

2019-01-29

0 627