← 返回题目列表

AtCoder · agc024_d

D. 同构怪胎

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

分数: 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