問題一覧 > 通常問題

No.1789 Tree Growing

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : chocorusk / テスター : heno239
お気に入りにしたユーザー ProblemId : 6593 / 自分の提出
問題文最終更新日: 2021-12-17 11:16:12
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2021 (順位表) の他の問題:

Problem Statement

Rusk has a tree $T_1$ with $K$ vertices. The vertices are numbered $1, 2, \ldots , K$, and the $i$-th edge ($1\leq i \leq K-1$) connects vertex $a_i$ and vertex $b_i$. Initially, all edges of $T_1$ are painted red.

Rusk can perform the following $2$ types of operations on $T_1$ any number of times, in any order. It is also allowed to perform no operations at all.

  1. Choose a vertex $v$ of $T_1$. Add a new vertex $w$ and add a blue edge $(v, w)$.
  2. Choose an edge $(u, v)$ of $T_1$. Let $x$ be the color of edge $(u, v)$. Add a new vertex $w$, remove edge $(u, v)$, and add edges $(u, w), (v, w)$ of color $x$.

Rusk has a favorite tree $T_2$. $T_2$ has $N$ vertices, numbered $1, 2, \ldots , N$, and the $i$-th edge ($1\leq i \leq N-1$) connects vertex $c_i$ and vertex $d_i$.

Rusk's goal is to make $T_1$ isomorphic to $T_2$ (edge colors are not considered when determining isomorphism). Determine whether this is possible, and if it is, find the maximum number of red edges in the final $T_1$.

Input

$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$
  • The graphs given in the input are all trees.
  • All input values are integers.

Output

If it is impossible to make $T_1$ isomorphic to $T_2$, print -1. If it is possible, print the maximum possible number of red edges in the final $T_1$.

Sample

Sample 1
Input
4
1 3
3 4
2 3
6
4 5
1 6
1 3
2 5
1 5
Output
4

If the operations are performed as follows, $T_1$ becomes isomorphic to $T_2$, and among the edges of the final $T_1$, the $4$ edges other than edge $(5, 6)$ are red.

  • Perform operation $2$. Add a new vertex $5$, remove the red edge $(1, 3)$, and add red edges $(1, 5)$, $(3, 5)$.
  • Perform operation $1$. Add a new vertex $6$ and add a blue edge $(5, 6)$.

Sample 2
Input
4
1 4
3 4
2 4
5
4 5
2 3
1 4
1 2
Output
-1

No matter how the operations are performed, $T_1$ cannot be made isomorphic to $T_2$.

Sample 3
Input
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
Output
7

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