問題一覧 > 通常問題

No.912 赤黒木

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : ei1333333ei1333333 / テスター : たぴちゃんたぴちゃん
12 ProblemId : 3332 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-08 16:53:41

問題文

$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} \color{black}{2} \Rightarrow 4$ の順に移動します。($\Rightarrow$ は黒い辺, $\color{red}{\Rightarrow}$ は赤い辺を表します)

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

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

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