wxyww

未归档

精品(28) 题解(65)

/ 注册

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

树的重心

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

树的重心学习笔记

2019-01-29

0 602

点分治

思想点分治的思想其实就是在树上进行分治。从而降低复杂度。每次找到一个点，对其进行处理，然后删除这个点，对剩下的子树进行递归处理。因为重心的每个儿子的大小不超过\(\frac{n}{2}\)，所以如果这个点是重心的话，就可保证递归层数最多为log层。实现在弄懂点分治思想的情况下，点分治...

树的重心

2019-01-30

0 543

树的重心

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

树的重心学习笔记

2019-01-29

0 485