CF1338B Edge Weight Assignment

给定一棵有 $n$ 个顶点的无权树。你需要为每条边分配一个正权值，使得满足以下条件： - 对于树中任意两个不同的叶子 $v_{1}$ 和 $v_{2}$，$v_{1}$ 到 $v_{2}$ 的简单路径上所有边的权值的按位异或（bitwise XOR）结果必须等于 $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} < b_{i} \le n$），表示在 $a_{i}$ 和 $b_{i}$ 之间有一条边。保证给定的图是一棵有 $n$ 个顶点的树。

输出两个整数，分别表示在合法分配下 $f$ 的最小值和最大值。保证在给定的约束下总是存在合法分配。

在第一个例子中，每种最小值和最大值的可能分配如下图所示。当然，每种最小值和最大值的分配方式都不唯一。  在第二个例子中，每种最小值和最大值的可能分配如下图所示。对于这棵树，合法分配的 $f$ 值总是 $3$。  在第三个例子中，每种最小值和最大值的可能分配如图所示。当然，每种最小值和最大值的分配方式都不唯一。  由 ChatGPT 4.1 翻译