No.912 赤黒木

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 23
作問者 : TaprisちゃんTaprisちゃん / テスター : たぴちゃんたぴちゃん
7 ProblemId : 3332 / 出題時の順位表

問題文

$N$ 個の頂点と $N - 1$ 本の赤い辺, $N - 1$ 本の黒い辺からなる無向連結グラフがあります。

頂点には $1$ から $N$ までの番号が付けられていて, 赤い辺のうち $i$ 番目の辺は頂点 $A_i$ と $B_i$ を, 黒い辺のうち $j$ 番目の辺は頂点 $C_j$ と $D_j$ を双方向に結んでいます。

赤い辺のみからなるグラフと黒い辺のみからなるグラフは, それぞれ連結であることが保証されています。

これから好きな頂点を始点として, 今いる頂点に繋がっている辺を自由に一つ選び, その辺を通って隣接する頂点に移動することを何回か行います。

赤い辺は何度通っても壊れませんが, 黒い辺は一度通ると壊れて通れなくなることが分かっています。

黒い辺をすべて壊すために必要な移動回数の最小値を求めてください。

入力

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$:$
$A_{N-1}$ $B_{N-1}$
$C_1$ $D_1$
$C_2$ $D_2$
$:$
$C_{N-1}$ $D_{N-1}$
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i, B_i \leq N$
  • $1 \leq C_j, D_j \leq N$
  • 赤い辺のみからなるグラフと黒い辺のみからなるグラフはそれぞれ連結
  • 入力はすべて整数

出力

$1$ 行に答えを出力してください。

サンプル

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

$5$ 回の移動で黒い辺をすべて壊すことができます。

例えば, 頂点 $3 \Rightarrow 4 \Rightarrow 5 \Rightarrow 1 \color{red}{\Rightarrow} 2 \Rightarrow 4$ の順に移動します。($\Rightarrow$ は黒い辺, $\color{red}{\Rightarrow}$ は赤い辺を表します)

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

赤い辺を一度も通らない場合もあります。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。