AT_agc024_d [AGC024D] Isomorphism Freak

[problemUrl]: https://atcoder.jp/contests/agc024/tasks/agc024_d 木 $ G $ の頂点を何色かで塗り分ける方法が *良い彩色* であるとは、同じ色で塗られたどの $ 2 $ つの頂点 $ u,v $ に対しても、 $ G $ を $ u $ を根とする根付き木として見た木と $ v $ を根とする根付き木として見た木が同型であることを指します。 また、$ G $ の *カラフルさ* とは、$ G $ の良い彩色で使われる色の種類数の最小値を指します。 $ N $ 頂点の木が与えられます。頂点には $ 1 $ から $ N $ までの番号がついており、$ i $ 本目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 この木に以下の操作を何度か繰り返し施し、木 $ T $ を作ります。 - 新たな頂点を $ 1 $ つ作る。現在の木の頂点をひとつ選び、その頂点と新しく作った頂点を辺で結ぶ。 $ T $ としてありうるもののカラフルさの最小値を求めてください。 さらに、その最小値を達成する木 $ T $ の葉(次数 $ 1 $ の頂点)の数の最小値を出力してください。

N/A

N/A

### ノート $ G $ を $ u $ を根とする根付き木として見た木と $ v $ を根とする根付き木として見た木が同型であるとは、 $ G $ の頂点集合からそれ自身への全単射な写像 $ f_{uv} $ であって、以下を満たすものが存在することを指します。 - $ f_{uv}(u)=v $ - どの $ 2 $ 頂点の組 $ (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) $ - 与えられるグラフは木である ### Sample Explanation 1 頂点 $ 6 $ を用意し、頂点 $ 2 $ と結んだとき、頂点 $ (1,4,5,6) $ を赤で、頂点 $ (2,3) $ を青で塗る彩色は良い彩色です。 $ 1 $ 色で全頂点を塗る彩色は良い彩色ではないので、作った木のカラフルさは $ 2 $ となることが分かります。 この場合が最適であり、葉は $ 4 $ つあるので、$ 2 $ と $ 4 $ を出力します。