AT_agc024_d [AGC024D] Isomorphism Freak

将树 $G$ 的顶点用若干种颜色进行染色，如果对于任意两个被染成同一种颜色的顶点 $u,v$，以 $u$ 为根的有根树和以 $v$ 为根的有根树同构，则称这种染色方式为*良好染色*。 树 $G$ 的*多彩度*定义为 $G$ 的所有良好染色中所使用颜色种类数的最小值。 给定一棵有 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $a_i$ 和顶点 $b_i$。你可以多次进行如下操作，构造出一棵新的树 $T$： - 新建一个顶点，从当前树中选择一个顶点，将新顶点与其通过一条边连接。 请你求出所有可能构造出的树 $T$ 中，多彩度的最小值。并且，在达到该最小多彩度的情况下，输出此时树 $T$ 的叶子（度数为 $1$ 的顶点）数的最小值。

输入以如下格式从标准输入读入： > $N$ > $a_1$ $b_1$ > $a_2$ $b_2$ > $\vdots$ > $a_{N-1}$ $b_{N-1}$

请输出两个整数，用空格隔开。首先输出所有可能构造出的树 $T$ 中的最小多彩度，然后输出在达到该最小多彩度时树 $T$ 的最小叶子数。 在本题的约束下，输出的值保证不会超过 $64$ 位有符号整数的范围。

### 说明 以 $u$ 为根的有根树和以 $v$ 为根的有根树同构，指的是存在 $G$ 的顶点集合到自身的一个双射 $f_{uv}$，满足： - $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)$ - 给定的图保证是一棵树 ### 样例说明 1 如果新建顶点 $6$ 并与顶点 $2$ 相连，将顶点 $(1,4,5,6)$ 染成红色，顶点 $(2,3)$ 染成蓝色，这是一种良好染色。用 $1$ 种颜色染所有顶点不是良好染色，因此该树的多彩度为 $2$。这种情况下叶子数为 $4$，所以输出 $2\ 4$。 由 ChatGPT 4.1 翻译