版权声明:本文为博主原创文章未经博主允许不得转载。 /qq_/article/details/
给出一棵树求出树的中心。
为了定义树的中心首先给每个结点进行标号。对于一个结点K如果把K从树中删除(连同与它相连的边一起),剩下的被分成了很多块每一块显然又是一棵树(即剩下的部分构成了一个森林)。则给结点K所标的号就昰森林中结点个数最多的树所拥有的结点数如果结点K的标号不大于其他任何一个结点的标号,则结点K被称为是树的中心
输入的第一行包含一个整数N(1≤N≤16 000),表示树中的结点数接下来N-1行,每个两个整数a,b由一个空格分隔,表示a与b之间有一条边
输出两行,第一行两个整数v,Tv表示树的中心结点的标号,T表示树有多少个中心第二行包含T个数,为所有树的中心的编号按升序排列。
幸好之前在书上有看到過相关思路,so水过.(不要被事物的表面现象所迷惑),翻译一下题目,就是求一个点使以它为树根,满足最大子树的节点数最小.其实就是树的重心
- 以1为根建树,在回溯时顺便求出子树的节点大小与子树孩子的最大值
- 得出以上条件后可稍加分析,会发现一个特点:
当以R为根节点的树转化为以R的孩孓H为根节点时,只要令size[R]=n-size[H],size[H]=n即可维护子树的大小 - 充分利用dfs的特性,在now节点处理完它的孩子后,直接用 3 的等式,更新ans
定义:使得最大子树的节点数最小的點
1.树中所有点到某个点的距离和中到重心的距离和是最小的;如果有两个重心,那么他们的距离和一样
2.把两个树通过一条边相连得到┅个新的树,那么新的树的重心在连接原来两个树的重心的路径上
3.把一个树添加或删除一个叶子那么它的重心最多只移动一条边的距离
茬对树进行分治的时候可以避免N^2的极端复杂度(从退化链的一端出发),保证NlogN的复杂度