問題一覧 > 通常問題

No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 71
作問者 : amesyu / テスター : noshinn lmorinn 遭難者
ProblemId : 12320 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-18 16:35:09

問題文

$N$ 頂点の無向木 $T$ が与えられます。頂点には $1, 2, \cdots, N$ の番号が付いており、各 $i \ (1 \leq i \leq N-1)$ について $i$ 番目の辺は 頂点 $u_i$ と 頂点 $v_i$ を結んでいます。
以下の条件を満たす頂点 $x$ が存在するようなグラフを綺麗なウニ木と呼びます。

  • グラフは無向木である。
  • 頂点 $x$ を根とした根付き木における葉の集合を $S$ とするとき、以下の条件をすべて満たす。
    • $S$ に含まれる異なる頂点組 $(u, v)$ の最小共通祖先は $x$ である。
    • $u \in S$ に対して $x$ と $u$ の距離 $d(x, u)$ はすべて等しい。
例えば以下のようなグラフは綺麗なウニ木です。例として条件を満たすような頂点 $x$ を紺色で表示しています。

一方で以下のようなグラフは綺麗なウニ木ではありません。

$T$ の部分グラフのうち、綺麗なウニ木の頂点数の最大値を求めてください。なお、本問題の制約下で $T$ の部分グラフに綺麗なウニ木が存在します。

制約

  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq u_i \lt v_i \leq N$
  • 与えられるグラフは無向木である。
  • 入力はすべて整数

    • 入力

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

    出力

    綺麗なウニ木の頂点数の最大値を求めてください。

    サンプル

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

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

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