問題一覧 > 通常問題

No.1752 Up-Down Tree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : rianoriano / テスター : saksak
2 ProblemId : 6493 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-28 17:55:13

問題文

頂点 $1$ を根とする $N$ 頂点の木が与えられます。 あなたは、この木と $1$ つの駒を使って、以下の操作を行います。

  1. 初めに頂点を $1$ つ選択し、駒を置く。
  2. 駒を、今まで置いたことのない頂点に移動させることを繰り返す。ただし、初めに駒を置いた直後の移動を $1$ 回目として、 奇数回目の移動では「その時点で駒が置かれている頂点の祖先にあたる頂点」に、 偶数回目の移動では「その時点で駒が置かれている頂点の子孫にあたる頂点」に移動させる。
  3. 移動可能な頂点が存在しない場合、操作を終了する。
この一連の操作を一度だけ終了まで行う過程で、駒が置かれたことのある頂点の数をあなたの得点とします。 あなたが得られる得点の最大値を求めてください。
ただし、 $N$ 頂点の木の $N-1$ 本の辺のうち $i$ 本目の辺は、入力で与えられる $A_i$ と $B_i$ を結んでいるものとします。 また、頂点 $u$, $v$ に対して「 $u$ が $v$ の祖先である」および「 $v$ が $u$ の子孫である」とは、どちらも「 $1$ と $v$ を結ぶ最短経路上に $u$ が存在する」ことをいいます。

入力

$N$
$A_1\ B_1$
$A_2\ B_2$
...
$A_{N-1}\ B_{N-1}$

  • $1\leq N\leq 10^5$
  • $1\leq A_i,B_i\leq N$ $(1\leq i\leq N-1)$
  • 与えられるグラフは木である
  • 入力は全て整数である

出力

あなたが得られる得点の最大値を整数で出力してください。 最後に改行してください。

サンプル

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

与えられた木は、下の図のような構造をしています。 あなたは例えば $3$→$1$→$7$→$4$→$6$→$2$→$5$ のような順で駒を移動させると、全ての頂点に対して駒を置かれたことがあるようにできます。 ここで、同じ頂点に二度駒を置くことは許されませんが、既に駒を置いた頂点を飛び越えて移動させることは可能であることに注意してください。

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

与えられた木は、下の図のような構造をしています。 あなたは適切な順で操作を行うと、$8$,$9$ を除く頂点全てに一度駒を置くことができます。 $8$,$9$ に一度以上駒を置く場合、どのようにしても $6$ 点以下の得点となりますので、$7$ 点が最善です。

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