나무 위의 구슬

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

요약

각 정점에 상자가 있고 구슬의 총 개수가 정점 수와 같은 루트 트리에서, 간선을 따라 구슬을 옮겨 모든 상자에 구슬이 정확히 하나씩 있게 하는 최소 이동 횟수를 구한다.

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

문제

루트가 있는 트리의 각 정점 위에 상자가 하나씩 놓여 있다. 정점은 $1$ 부터 $n$ 까지 번호가 매겨져 있으며, $1 \le n \le 10000$ 이다. 각 상자에는 구슬이 몇 개 들어 있거나 비어 있을 수 있고, 트리 전체에 놓인 구슬의 총 개수는 정확히 $n$ 개이다.

한 번의 이동은 어떤 상자에 들어 있는 구슬 하나를 트리에서 인접한 정점(부모 또는 자식)의 상자로 옮기는 것을 뜻한다. 모든 상자에 들어 있는 구슬의 개수를 정확히 $1$ 개로 만들기 위해 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫째 줄에는 정점의 개수 $n$ 이 주어진다. 이어지는 $n$ 개의 줄에는 각 정점의 정보가 한 줄씩 주어진다. 한 줄에는 정점 번호 $v$ , 처음에 정점 $v$ 의 상자에 들어 있는 구슬의 개수, 그리고 $v$ 의 자식 수 $d$ 가 차례로 주어지고, 그 뒤에 $v$ 의 자식 번호가 $d$ 개 주어진다.

$n = 0$ 인 줄이 입력의 끝을 나타내며, 이 경우는 처리하지 않는다.

출력

각 테스트 케이스마다 모든 상자의 구슬 개수를 $1$ 개로 만들기 위해 필요한 최소 이동 횟수를 한 줄에 하나씩 출력한다.

예제7

예제 1

입력

9
1 2 3 2 3 4
2 1 0
3 0 2 5 6
4 1 3 7 8 9
5 3 0
6 0 0
7 0 0
8 2 0
9 0 0
9
1 0 3 2 3 4
2 0 0
3 0 2 5 6
4 9 3 7 8 9
5 0 0
6 0 0
7 0 0
8 0 0
9 0 0
9
1 0 3 2 3 4
2 9 0
3 0 2 5 6
4 0 3 7 8 9
5 0 0
6 0 0
7 0 0
8 0 0
9 0 0
0

예상 출력

7
14
20

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

예제 6

입력

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

예상 출력

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