Skip to content

1112: 分割树

题目

题目描述

现在有一棵树$T$,有$N$个节点,我们想通过去掉一个节点p来把T分割成更小的树,并且满足每个小树中的节点数不超过$n/2$。

请根据输入的树来输出所有可能的p的号码。

输入格式

第1行:一个整数$N$,代表有$N$个节点,且每个节点的编号为$1,2,...,N$。

第2~N行:每行两个整数$x$,$y$,代表节点$x$和节点$y$之间连通。

输出格式

从小到大一次输出满足条件的p的号码,每行1个可行解。

样例输入

text 10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8

样例输出

text 3 8

当3号节点/8号节点被删除,此时剩下的树的节点数分别为2、2、5,均不大于10/2=5,而其他的节点中,无论哪一个,总有一棵树的大小大于等于6。

数据范围

$N \leq 10000$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!