有一枚蛋糕可能被lqq赋予了魔法,它在导办门口长成了一棵蛋糕树!lqq希望站到蛋糕树的重心和大家合影,希望你帮忙找到他应该站的位置。
对于树中的任意节点,去掉该节点可使产生的子树的节点数中的最大值最小,则该节点定义为树的重心。
一棵树可能存在多个重心。
举两个例子:
例1
上图中有一个重心:号节点(将其去除后,树分离成三个连通块,大小分别为,最大的一块大小为(如下图)
另一个比较像重心的点是,但将其去除后树分离成大小为的三个连通块,最大一块大小为,所以号节点不是重心(如下图)
例2
上图中有两个重心,号节点和号节点都可以成为重心
现在有一个个节点的树,要求支持动态加边,删边,求出当前森林中的所有重心。