트리 가지치기

면접 대비

시간 제한2초메모리 제한512 MB

요약

색이 칠해진 이진 트리가 주어질 때, 부분 트리를 잘라내어 흰 노드에서 검은 노드를 뺀 값이 정확히 D가 되도록 하면서 자르는 횟수를 최소로 구한다.

난이도: 보통10점 중 6점
유형: 트리, 동적 계획법, DFS, 재귀
정답자: 아직 제출이 없습니다

문제

각 노드가 최대 두 개의 자식을 가지는, 루트가 있는 트리가 주어진다. 노드는 총 $N$ 개이며, 각 노드는 검은색 또는 흰색이다. '가지치기(prune)'란 한 노드와 그 노드를 루트로 하는 서브트리를 트리에서 통째로 삭제하는 연산이다. 정수 $D$ 가 주어질 때, (흰색 노드의 수) − (검은색 노드의 수)가 정확히 $D$ 가 되는 트리를 만들기 위해 필요한 '가지치기'의 최소 횟수를 구하여라. 만들 수 없다면 불가능함을 판정하여라.

입력

첫째 줄에 트리의 노드 수 $N$ ( $1 \le N \le 300$ )과 목표 차이 $D$ ( $-N \le D \le N$ )가 공백으로 구분되어 주어진다. 이어서 각 노드를 설명하는 $N$ 개의 블록이 주어진다. 각 블록의 첫째 줄에는 세 정수, 즉 노드의 번호( $0$ 이상 $N-1$ 이하의 서로 다른 정수), 노드의 색( $1$ 이면 흰색, $0$ 이면 검은색), 그리고 자식의 수 $C$ 가 주어진다. 이어지는 $C$ 개의 줄에는 각각 그 노드의 자식 하나의 번호가 주어진다. 트리의 루트는 번호가 $0$ 인 노드이다.

출력

한 줄에 문제에서 설명한 '가지치기'의 최소 횟수를 출력한다. 목표 차이 $D$ 를 만들 수 없다면 $-1$ 을 출력한다.

예제3

예제 1

입력

예상 출력

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