問題一覧 > 通常問題

No.1928 Make a Binary Tree

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 41
作問者 : harurunharurun / テスター : 👑 KazunKazun
5 ProblemId : 7403 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-07 12:26:21

コンテスト終了後に★3.5に変更しました。

問題文

$N$ 頂点の根付き木があり、頂点には $1\sim N$ の番号が付いています。根は頂点 $1$ です。

$i$ 番目の辺は、頂点 $x_i$ と 頂点 $y_i$ を結びます。

あなたは以下の操作をいずれも好きな回数好きな順序で操作することができます。

  • 操作A: ある頂点 $v$ を選ぶ。頂点 $v$ の親を頂点 $u$、頂点 $u$ のある祖先を頂点 $w$ とする。$v$ と $u$ を結ぶ辺を削除し、$v$ と$w$ を結ぶ辺を追加する。
  • 操作B: ある頂点 $v$ を選ぶ。頂点 $v$ の親を頂点 $u$ とする。$v$ と $u$ を結ぶ辺を削除し、$v$ を根とする部分木に含まれる辺と頂点をすべて削除する。
  • (削除した辺や頂点は使えません。また、$v$ に親が存在しない場合は操作を行えません。)

あなたの目標は、これらの操作で頂点の個数が最大になるように頂点 $1$ を根とする二分木を作成することです。

作成した二分木の頂点の個数の最大値を求めてください。


▼頂点 $v$ の祖先とは? 頂点 $v$ と 根の最短パス上の頂点を頂点 $v$ の祖先と言います。

入力

$N$
$x_1\ y_1$
$\vdots$
$x_{N-1}\ y_{N-1}$
  • $1$ 行目に頂点の個数 $N$ が与えられる
  • $2\sim N$ 行目に $x_i$ と $y_i$ が空白区切りで与えられる

制約

  • $1≤N≤2\times 10^5$
  • $1≤x_i,y_i≤N$
  • 入力はすべて整数である
  • 与えられるグラフは木である

出力

答えを1行に出力してください。最後に改行してください。

サンプル

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

与えられた木は二分木です。よって何も操作しないときに最大です。

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

頂点 $4$ に操作Bを行うと二分木になり、これが最大です。

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

頂点 $5$ に操作Aを行い、祖先である頂点 $1$ と結ぶと最大になります。

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