← 返回题目列表

Codeforces · 1338/B

B. 边权重分配

中文机器翻译题面 查看原题

您有 $$$n$$$ 个顶点的未加权树。您必须为每条边分配正权重,以便满足以下条件:

- 对于该树的每两个不同的叶子 $$$v_{1}$$$ 和 $$$v_{2}$$$,$$$v_{1}$$$ 和 $$$v_{2}$$$ 之间的简单路径上所有边的权重按位异或必须等于 $$$0$$$。

请注意,您可以输入非常大的正整数(例如 $$$10^{(10^{10})}$$$)。

保证在给定的约束下此类分配始终存在。现在让我们将 $$$f$$$ 定义为分配中不同权重的数量。

在此示例中,分配是有效的,因为每对叶子之间的所有边权重的按位异或为 $$$0$$$。这里$$$f$$$ 值为$$$2$$$,因为有$$$2$$$ 不同的边权重($$$4$$$ 和$$$5$$$)。在此示例中,分配无效,因为顶点 $$$1$$$ 和顶点 $$$6$$$ ($$$3, 4, 5, 4$$$) 之间的所有边权重的按位异或不是 $$$0$$$。

给定树的 $$$f$$$ 的最小和最大可能值是多少?查找并打印两者。

输入

第一行包含整数 $$$n$$$ ($$$3 \le n \le 10^{5}$$$) — 给定树中的顶点数。

接下来的 $$$n-1$$$ 行中的第 $$$i$$$ 包含两个整数 $$$a_{i}$$$ 和 $$$b_{i}$$$ ($$$1 \le a_{i} \lt b_{i} \le n$$$) - 这意味着 $$$a_{i}$$$ 和 $$$a_{i}$$$ 之间有一条边$$$b_{i}$$$。保证给定的图形成 $$$n$$$ 个顶点的树。

输出

打印两个整数 - $$$f$$$ 的最小和最大可能值可以通过给定树的有效分配得出。请注意,在给定的约束下总是可以进行分配。

示例

输入 #1

6
1 3
2 3
3 4
4 5
5 6

输出 #1

1 4

输入 #2

6
1 3
2 3
3 4
4 5
4 6

输出 #2

3 3

输入 #3

7
1 2
2 7
3 4
4 7
5 6
6 7

输出 #3

1 6

注意

在第一个示例中,下图描述了每个最小值和最大值的可能分配。当然,每个最小值和最大值都有多种可能的分配。

在第二个示例中,每个最小值和最大值的可能分配如下图所示。该树的有效赋值 $$$f$$$ 值始终为 $$$3$$$。

在第三个示例中,下图描述了每个最小值和最大值的可能分配。当然,每个最小值和最大值都有多种可能的分配。