No.2532 Want Play More
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 85
作問者 : hirayuu_yc / テスター : 👑 AngrySadEight
タグ : / 解いたユーザー数 85
作問者 : hirayuu_yc / テスター : 👑 AngrySadEight
問題文最終更新日: 2023-11-04 06:15:24
問題文
$N$ 頂点の木があり、頂点には $1,2,...,N$ と番号が振られています。
$i$ 番目の辺は頂点 $a_i$ と $b_i$ をつないでいます。
HalcとSappはこの木と駒を使ってゲームをします。
進行は以下の通りです。
- はじめ、頂点 $1$ に駒がある。
- HalcとSappが交互に駒を隣の頂点へ動かす。複数の行き先がある場合はどこに行ってもよい。
- 一回通った頂点には二度と立ち入ることができない。
- 動けなくなったらゲーム終了。
どちらかが駒を動かすのを $1$ ターンと数えます。
Halcはゲームが終了するまでのターン数を最大化、Sappは最小化しようとしています。
Halcが先手、後手の場合それぞれにおいて、両者が最適に行動した時のゲームが終了するまでのターン数を出力してください。
入力
$N$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_{N-1}$ $b_{N-1}$
- $1\leqq N\leqq 2\times 10^5$
- $1\leqq a_i,b_i\leqq N$
- 与えられるグラフは木である
- 入力はすべて整数
出力
2行出力してください。
1行目にはHalcが先手の場合、2行目にはHalcが後手の場合のターン数を出力してください。
サンプル
サンプル1
入力
6 1 2 2 3 3 4 3 5 5 6
出力
4 3
Halcが先手の場合、例えば以下のような進行が考えられます。
- Halcが駒を頂点 $2$ に動かす
- Sappが駒を頂点 $3$ に動かす
- Halcが駒を頂点 $5$ に動かす
- Sappが駒を頂点 $6$ に動かす
- 駒を動かせないのでゲームが終了する
実は、これは両者が最善に動いており、ターン数は $4$ です。
ちなみに、Halcが後手の場合は $3$ ターンで終わります。
サンプル2
入力
4 1 2 1 3 1 4
出力
1 1
最善の行動が複数ある場合もあります。
サンプル3
入力
1
出力
0 0
頂点が一つの場合もあります。この場合、辺の情報は与えられません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。