AT_abc293_h [ABC293Ex] Optimal Path Decomposition

[problemUrl]: https://atcoder.jp/contests/abc293/tasks/abc293_h $ N $ 頂点の木が与えられます。頂点には $ 1 $ から $ N $ までの番号がついており、$ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 各頂点に以下の条件を満たすように色を塗ることができる整数 $ K $ の最小値を求めてください。ただし、使える色の種類数に制限はありません。 - 各色について、その色で塗られた頂点の集合は連結で単純パスをなす - 任意の木上の単純パスについて、そのパス内に含まれる頂点に塗られた色の種類数は $ K $ 以下

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i,\ B_i\ \leq\ N $ - 与えられるグラフは木 - 入力はすべて整数 ### Sample Explanation 1 $ K\ =\ 3 $ のとき、頂点 $ 1,2,3,4,5 $ を色 $ 1 $、頂点 $ 6 $ を色 $ 2 $、頂点 $ 7 $ を色 $ 3 $ で塗るなどの方法で条件を満たすことができます。 $ K\ \leq\ 2 $ とすると条件を満たす色の塗り方は存在しないので答えは $ 3 $ です。