시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB11119.091%

문제

In preparation for the Swedish Coding Cup Finals, the organizing committee is decorating the hall for the award ceremony with beautiful juniper trees. They have designed an arrangement of $N$ trees, each with a specific look. As the resident arborist of the competition, it's your job to fix the trees.

You ordered $M$ trees, and the shipment arrived a minute ago. It may be the case that you can't pick $N$ trees of the exact right look out of these trees. In this case, you must cut off some branches on some trees in order to transform their looks into those required in the tree arrangement. There's a slight problem -- the contest just started, so you need to fix those trees up right now before the award ceremony!

Formally, a tree consists of a root, from which a number of branches (possibly none!) extend. Each branch ends at a point called a vertex, from which any number of new branches can extend. Two trees look the same if they have the same structure of branches and vertices. Note that the order in which a set of branches grows from a vertex does not matter.

To change the layout of a tree, you can use your trusty lopper to cut off branches that grow from a vertex, one branch at a time. Branches can be cut from any part of the tree: cutting a branch makes the whole subtree below it fall off. Since you're low on time, you'd prefer to do this as fast as possible. If you choose and cut $N$ of the trees optimally, how many cuts do you need to make in total?

입력

The first line contains two integers: $N$ -- the number of trees in the arrangement ($1 \le N \le 500$), and $M$ -- the number of trees you have ordered ($N \le M \le 500$).

Then $N + M$ descriptions of the trees follow -- first the $N$ trees in the arrangement, followed by the $M$ trees you had ordered. A tree description starts with an integer $0 \le B$ -- the number of branches of the tree. The next line contains $B$ integers, $a_1$, $a_2$, ..., $a_B$, where $a_i < i$. Each integer $a_i$ means that there is a branch between vertex $a_i$ and vertex $i$. If a branch grows from the root, this number is $0$.

There are at most $1000$ branches in total among the $N + M$ trees. It is guaranteed that it's possible to transform the trees in the described manner.

출력

Output a single integer -- the minimal number of edges you must cut to transform the layout of $N$ of the ordered trees into those of the trees in the arrangement.

서브태스크

번호 배점 제한
1 10

Each vertex (including the root) has either $0$ or $1$ branches growing from it.

2 25

$N = M = 1$, and each vertex (including the root) has either $0$, $1$ or $2$ branches growing from it.

3 25

No additional constraints.

예제 입력 1

2 3
3 0 0 0
4 0 1 2 0
2 0 1
3 0 0 0
5 0 0 1 0 3

예제 출력 1

1

예제 입력 2

5 5
1 0
3 0 1 2
4 0 1 2 3
3 0 1 2
5 0 1 2 3 4
2 0 1
3 0 1 2
5 0 1 2 3 4
4 0 1 2 3
5 0 1 2 3 4

예제 출력 2

2

예제 입력 3

1 1
2 0 0
4 0 0 1 1

예제 출력 3

2

힌트

In the first sample, we ordered three trees and need to construct two trees. The second of the ordered trees exactly matches the first tree in the arrangement, so we can choose it without performing any cuts. The third of the ordered trees is similar to the second tree in the arrangement, except it has an extra branch from the root. Thus, we only need to perform a single cut to transform the tree.

출처

Contest > Swedish Coding Cup > Swedish Coding Cup Finals 2021 B번

  • 문제를 만든 사람: Johan Sannemo, Mattias Akke

채점 및 기타 정보

  • 예제는 채점하지 않는다.