問題一覧 > 通常問題

No.1789 Tree Growing

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : 👑 chocoruskchocorusk / テスター : heno239heno239
0 ProblemId : 6593 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-17 11:16:12

問題文

ラスク君は $K$ 頂点からなる木 $T_1$ を持っています。頂点には $1, 2, \ldots , K$ の番号がついており、$i$ 番目 ($1\leq i \leq K-1$) の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。はじめ、$T_1$ のすべての辺は赤色で塗られています。

ラスク君は、$T_1$ に次の $2$ 種類の操作を好きな順に何回でも行うことができます。全く操作を行わなくても構いません。

  1. $T_1$ の頂点 $v$ を選ぶ。新しい頂点 $w$ を追加し、青色の辺 $(v, w)$ を追加する。
  2. $T_1$ の辺 $(u, v)$ を選ぶ。辺 $(u, v)$ の色を $x$ とする。新しい頂点 $w$ を追加し、辺 $(u, v)$ を取り除いて、色 $x$ の辺 $(u, w), (v, w)$ を追加する。

ラスク君には、お気に入りの木 $T_2$ があります。$T_2$ は $N$ 頂点からなり、頂点には $1, 2, \ldots , N$ の番号がついていて、$i$ 番目 ($1\leq i \leq N-1$) の辺は頂点 $c_i$ と頂点 $d_i$ を結んでいます。

ラスク君の目標は、$T_1$ を $T_2$ と同型にすることです (同型判定において、辺の色は考慮しません)。これが可能かどうか判定し、可能な場合は最終的な $T_1$ における赤色の辺の本数の最大値を求めてください。

入力

$K$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_{K-1}\ b_{K-1}$
$N$
$c_1\ d_1$
$c_2\ d_2$
$\vdots$
$c_{N-1}\ d_{N-1}$

  • $2\leq K\leq N\leq 100$
  • $1\leq a_i < b_i\leq K$
  • $1\leq c_i < d_i\leq N$
  • 入力で与えられるグラフはいずれも木である。
  • 入力はすべて整数である。

出力

$T_1$ を $T_2$ と同型にすることが不可能な場合は -1 と出力してください。可能な場合は、最終的な $T_1$ における赤色の辺の本数として考えられる最大値を出力してください。

サンプル

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

次のように操作を行うと、$T_1$ が $T_2$ と同型になり、最終的な $T_1$ の辺のうち、辺 $(5, 6)$ 以外の $4$ 本の辺は赤色となります。

  • 操作 $2$ を行う。新しい頂点 $5$ を追加し、赤色の辺 $(1, 3)$ を取り除いて、赤色の辺 $(1, 5)$, $(3, 5)$ を追加する。
  • 操作 $1$ を行う。新しい頂点 $6$ を追加し、青色の辺 $(5, 6)$ を追加する。

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

どのように操作を行っても、$T_1$ を $T_2$ と同型にすることはできません。

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

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