4057. 不会吧不会吧不会这道题还有同学答案错误吧

单点时限: 1.0 sec

内存限制: 256 MB

这是一道提交答案题。

你需要构造一棵点数不大于 $5000$ 的树,并给出一种分治方法使得在这棵树上迭代层数小于根据子树大小分治的策略。

按子树大小的分治策略如下:

solve($T$):

$~~~~$若 $T$ 中没有边,返回。

$~~~~$枚举 $T$ 中的所有边,找到一条边 $e$,使得删去 $e$ 之后,形成的两棵子树含有的节点数的差的绝对值最小。

$~~~~$删去 $e$,形成两个子树 $T_1$, $T_2$。

$~~~~$solve($T_1$)

$~~~~$solve($T_2$)

输入格式

没有输入。

输出格式

你可以选择 Text 选项并直接提交答案,也可以提交一个可以生成答案的程序。

第一行,输出一个正整数 $n$,表示树的节点个数。

接下来 $n-1$ 行,每行两个正整数 $u,v$,表示一条连接节点 $u$ 和 $v$ 的边。

判题程序会根据你输出的边的顺序从前往后依次切断你给定的边,对新得到的两棵子树递归分治。

提示

你可以点击这里下载检验程序的 C++ 语言源代码。将你的解输入检验程序将会得到根据你的方案得到的递归深度和根据子树大小得到的递归深度。

你也可以点击这里下载适用于运行于 64 位 Windows 的二进制文件。

点击这里下载适用于 32 位 Windows 的二进制文件。

点击这里下载适用于 64 位 Linux 的二进制文件。

如果点击无法正常下载请尝试右击后另存为。

22 人解决,32 人已尝试。

22 份提交通过,共有 78 份提交。

5.1 EMB 奖励。

创建: 3 年,9 月前.

修改: 3 年,2 月前.

最后提交: 1 年,4 月前.

来源: EOJ Monthly 2021.3

题目标签