나무 다듬기

시간 제한1초메모리 제한1024 MB

요약

주문한 M그루 중 N그루를 골라 목표 나무 N그루와 하나씩 짝짓고, 가지를 잘라 모양을 맞출 때 필요한 최소 절단 수를 구합니다.

난이도: 보통10점 중 7점
유형: 트리, 동적 계획법, 그래프
정답자: 아직 제출이 없습니다

문제

스웨덴 코딩 컵 결승을 준비하며 조직위원회는 시상식장을 아름다운 향나무로 꾸미려 합니다. 위원회는 각각 고유한 모양을 가진 $N$ 그루의 나무로 이루어진 배치를 설계했습니다. 대회의 상주 수목 관리사인 당신이 할 일은 이 나무들을 고치는 것입니다.

당신은 $M$ 그루의 나무를 주문했고, 배송품은 1분 전에 도착했습니다. 배치와 정확히 같은 모양의 나무를 $N$ 그루 고르지 못할 수도 있습니다. 이 경우 일부 나무의 가지를 잘라 배치가 요구하는 모양으로 바꿔야 합니다. 대회가 막 시작되었으므로, 시상식 전에 지금 바로 나무를 고쳐야 합니다.

정확히 말하면, 나무는 뿌리에서 여러 가지(가지가 전혀 없을 수도 있음)가 뻗어 나온 형태입니다. 각 가지는 꼭짓점이라 불리는 점에서 끝나며, 그 꼭짓점에서는 새 가지가 몇 개든 뻗어 나올 수 있습니다. 가지와 꼭짓점의 구조가 같으면 두 나무는 같은 모양입니다. 한 꼭짓점에서 가지가 자라는 순서는 상관없습니다.

나무의 모양을 바꾸려면 믿음직한 전지가위로 꼭짓점에서 자라는 가지를 한 번에 하나씩 잘라낼 수 있습니다. 가지는 나무의 어느 부분에서든 자를 수 있습니다. 가지를 자르면 그 아래의 부분 나무 전체가 떨어집니다. 가능한 한 빨리 끝내고 싶습니다. $N$ 그루의 나무를 골라 최적으로 자른다면, 모두 몇 번 잘라야 합니까?

입력

첫 번째 줄에 두 정수 $N$ ( $1 \le N \le 500$ , 배치에 있는 나무의 수)과 $M$ ( $N \le M \le 500$ , 주문한 나무의 수)이 주어집니다.

이어서 $N + M$ 개의 나무 설명이 나옵니다. 먼저 배치의 나무 $N$ 개가 나오고, 그다음 주문한 나무 $M$ 개가 나옵니다. 나무 설명은 가지의 개수 $B \ge 0$ 로 시작합니다. 다음 줄에는 $B$ 개의 정수 $a_1, a_2, \ldots, a_B$ 가 주어지며, 모든 $i$ 에 대해 $a_i < i$ 입니다. $a_i$ 는 꼭짓점 $a_i$ 와 꼭짓점 $i$ 사이에 가지가 있다는 뜻입니다. 가지가 뿌리에서 자라면 이 값은 $0$ 입니다.

$N + M$ 개의 나무 전체에서 가지는 최대 $1000$ 개입니다. 설명한 방식으로 나무를 변형할 수 있다고 보장됩니다.

출력

주문한 나무 중 $N$ 그루를 배치의 나무 모양으로 바꾸는 데 필요한 최소 자르기 횟수, 즉 잘라야 하는 간선의 최소 개수를 하나의 정수로 출력합니다.

힌트

첫 번째 예제에서는 주문한 나무가 3그루이고, 만들어야 할 나무는 2그루입니다. 주문한 두 번째 나무는 배치의 첫 번째 나무와 정확히 같으므로, 자르지 않고 그대로 고를 수 있습니다. 주문한 세 번째 나무는 배치의 두 번째 나무와 비슷하지만, 뿌리에서 가지가 하나 더 나와 있습니다. 따라서 한 번만 잘라서 고칠 수 있습니다.

예제3

예제 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

예상 출력

예제 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

예상 출력

예제 3
입력
```
1 1
2 0 0
4 0 0 1 1
```
예상 출력
```
2
```