分数: 1100 点
问题陈述
树的顶点着色 G 被称为 着色良好 当,对于每对两个顶点 u 和 v 涂上同样的颜色,采摘 u 为根并采摘 v 作为根会导致同构有根树。
另外, 色彩 of G 被定义为良好着色中使用的不同颜色的最小可能数量。 G.
你有一棵树 N 顶点。顶点已编号 1 通过 N,以及 i第一条边连接顶点 a_i 和顶点 b_i。我们将构建一棵新树 T 通过在此树上重复以下操作一定次数:
- 通过使用边将新顶点连接到当前树中的顶点之一,将新顶点添加到树中。
找出 的最小可能色彩 T。 此外,打印叶子的最小数量(具有度数的顶点 1) 在树中 T 实现最低色彩度。
注释
短语“挑选 u 为根并采摘 v 因为树的根会导致同构有根树” G 表示存在双射函数 f_{uv} 来自顶点集 G 自身,以满足以下两个条件:
- f_{uv}(u)=v
- 对于每对两个顶点 (a,b),边缘 (a,b) 存在当且仅当边 (f_{uv}(a),f_{uv}(b)) 存在。
约束
- 2 \leq N \leq 100
- 1 \leq a_i,b_i \leq N(1\leq i\leq N-1)
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
:
a_{N-1} b_{N-1}
输出
打印两个整数,中间有一个空格。 首先,打印树的最小可能色彩 可以构建的 T 。 其次,打印实现该目标的树中叶子的最小数量。
可以证明,在这个问题的约束下,应该打印的值适合 64- 位有符号整数。
示例输入 1
5 1 2 2 3 3 4 3 5
示例输出 1
2 4
如果我们连接一个新顶点 6 到顶点 2,绘制顶点 (1,4,5,6) 红色并绘制顶点 (2,3) 蓝色是一种很好的颜色。 由于用单一颜色绘制所有顶点不是一个好的着色,我们可以看到这棵树的色彩是 2。 这实际上是最优解。有四片叶子,所以我们应该打印 2 和 4.
示例输入 2
8 1 2 2 3 4 3 5 4 6 7 6 8 3 6
示例输出 2
3 4
示例输入 3
10 1 2 2 3 3 4 4 5 5 6 6 7 3 8 5 9 3 10
示例输出 3
4 6
示例输入 4
13 5 6 6 4 2 8 4 7 8 9 3 2 10 4 11 10 2 4 13 10 1 8 12 1
示例输出 4
4 12