POJ 1655 Balancing Act

题意

求树的重心。

思路

树的重心的定义是:选树中某个点i当作树的根,所有子树中最大的那棵的大小是Si,整棵树中能令Si最小的那个点,就是树的重心。

求重心是作为树分治的一个环节出现的,只有保证了每一次点分治的位置都是重心才能保证树分治的复杂度为O(nlogn)。

求重心的想法是树dp,对于每个节点都要存储他所有孩子对应的子树中最大子树的大小,还要存储他的父亲是谁。求好了这些数据之后,按着定义,就可以知道谁是重心了。

代码

 

3 Comments

  1. […] 和这个题一致 […]

    Reply
  2. […] 请参考这个题和/或这个题 […]

    Reply
  3. […] POJ 1655 Balancing Act:求树的重心 […]

    Reply

Leave a Reply to POJ 2378 Tree Cutting | hahaschool Cancel reply

Scroll to top