問題一覧 > 通常問題

No.1976 Cut then Connect

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : magstamagsta / テスター : shino16shino16
5 ProblemId : 7942 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-08 19:55:45

問題文

$N$ 個の頂点の木が与えられます。木の頂点には $1$ から $N$ までの、辺には $1$ から $N-1$ までの番号が付けられています。

辺 $i \ (1 \leq i \leq N-1)$ は頂点 $u_i, v_i$ を結んでいます。


ここで、以下の操作を行います。

  • 与えられた木の無向辺のうち $1$ つを消す。グラフの連結成分の個数は $2$ になる。

    グラフの連結成分それぞれに対して連結成分に属する頂点を $1$ つずつ選び、その $2$ つの頂点を無向辺で繋ぐ。

この操作を行ってもグラフは木のままになります。操作後の木の直径として考えられるものの最小値を求めてください。


また木の直径とは、木に存在する $2$ つの頂点を繋ぐパスに含まれる辺の個数の最大値とします。

制約

  • $\displaystyle 2 \leq N \leq 10^5$
  • $\displaystyle 1 \leq u_i, v_i \leq N$
  • $\displaystyle u_i \neq v_j$
  • 入力はすべて整数である
  • 入力が表すグラフは木である

入力

入力は以下の形式で標準入力から与えられる。

$N$
$u_1\ \ v_1$
$u_2\ \ v_2$
$:$
$u_{N-1}\ \ v_{N-1}$

出力

求めた値を出力し、最後に改行せよ。

サンプル

サンプル1
入力
5
1 2
2 3
3 4
4 5
出力
3

頂点 $2$ と頂点 $3$ を結ぶ辺を消し、頂点 $2$ と頂点 $4$ を辺で結ぶと直径は $3$ となります。

直径を $2$ 以下にすることはできないため、これが最小値となります。

サンプル2
入力
2
1 2
出力
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。