P3563 [POI 2013] POL-Polarization

每个人都知道这只是时间问题。那么又如何呢？ 面对多年的威胁，这种危险成为了日常现实。 它失去了意义…… 今天，Bitotia 的 char Bittard 给 Byteotia 国王 Byteasar 的信被公开了。 Bitotia 要求吞并整个 Byteotia，否则将使用 Bit 极化磁铁（BPM）。 如果使用，BPM 将使 Byteotia 的每条道路变为单向。 敌人非常清楚，这可能会对极简的 Byteotia 基础设施造成致命打击——在每对城镇之间只有唯一的路径。 BPM 能对 Byteotia 的基础设施造成多大的破坏？ 确定在新的道路方向下，仍然可以从一个城镇到另一个城镇的最小和最大城镇对数。

标准输入的第一行给出一个整数 $n$ ($1 \leq n \leq 250\,000$)，表示 Byteotia 中的城镇数量。 接下来的 $n-1$ 行描述这些道路。 每行包含两个整数，$a$ 和 $b$ ($1 \leq a, b \leq n$)，表示目前仍为双向的直接道路连接城镇 $a$ 和 $b$。 在占总分 60% 的测试中，额外的约束 $n \leq 5\,000$ 成立；此外，在其中一些占总分 30% 的测试中，甚至有 $n \leq 1\,000$。

标准输出的第一行应打印两个整数。 第一个数字应为在道路极化后仍然可以连接的城镇对数的最小值，第二个数字应为最大值（尽管仅为单向）。

题面翻译由 ChatGPT-4o 提供。