No.1789 Tree Growing
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.
- Choose a vertex $v$ of $T_1$. Add a new vertex $w$ and add a blue edge $(v, w)$.
- 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もしくは右上の雲マークをクリックしてアカウントを作成してください。
chocorusk
heno239