Usoperanto

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

요약

각 단어가 많아야 한 단어를 수식하는 문장에서 모든 단어를 배열해 수식어와 피수식어 사이의 글자 수 합을 최소로 만들고, 그 최솟값을 구한다.

난이도: 어려움10점 중 8점
유형: 그리디, 트리, 정렬, DFS
정답자: 아직 제출이 없습니다

문제

Usoperanto는 Usoperanto Academy가 설계하고 관리하는 인공 구어이다. 이 학회는 공식 문서용으로 쓰이는 변형인 Strict Usoperanto를 확립하기 위한 연구를 진행 중이다.

Usoperanto에서 각 단어는 다른 단어를 최대 하나만 수식할 수 있고, 수식어는 항상 피수식어 앞에 온다. 예를 들어 명사 uso("진실")를 형용사 makka("전적인")가 수식할 때 사람들은 makka uso라고 말하지 uso makka라고는 말하지 않는다. 반면 같은 단어를 수식하는 여러 단어 사이의 순서에 관한 규칙은 없어서, uso를 형용사 beta("명백한")가 하나 더 수식하는 경우 사람들은 makka beta uso와 beta makka uso를 모두 말할 수 있다.

Strict Usoperanto에서는 수식 비용에 따라 어순이 제한된다. 구에 있는 단어들은 총 수식 비용이 최소가 되도록 배열해야 한다. 수식어와 피수식어의 각 쌍에는 두 단어 사이에 있는 글자 수만큼의 비용이 부여되고, 총 수식 비용은 구에 있는 모든 수식어-피수식어 쌍의 비용 합이다. 예를 들어 구 makka beta uso에서 makka와 uso 쌍은 beta(글자 네 개) 때문에 비용 4를 갖는다. beta와 uso 쌍은 사이에 단어가 없으므로 비용이 0이고, 따라서 makka beta uso의 총 수식 비용은 4이다. 마찬가지로 beta makka uso의 총 수식 비용은 5이다. "총 수식 비용 최소" 규칙을 적용하면 Strict Usoperanto에서는 makka beta uso가 beta makka uso보다 선호된다.

이 문제에서 여러분의 임무는 구에 있는 단어 집합이 주어졌을 때 Strict Usoperanto에서 올바른 어순을 찾아 총 수식 비용을 출력하는 프로그램을 작성하는 것이다.

입력

입력 형식은 다음과 같다.

N
M0 L0
...
MN-1 LN-1

첫째 줄에는 정수 N(1 ≤ N ≤ 106)이 주어진다. N은 구에 있는 단어의 수이다.

다음 N개 줄에는 각각 i번째 단어(0 ≤ i ≤ N-1)를 나타내는 두 정수 Mi(1 ≤ Mi ≤ 10)와 Li(-1 ≤ Li ≤ N - 1, Li ≠ i)가 주어진다. Mi는 그 단어의 글자 수이다. Li는 수식을 지정한다. Li = -1이면 아무 단어도 수식하지 않고, 그렇지 않으면 Li번째 단어를 수식한다.

아래 첫 번째 예제 입력은 uso-beta-makka 경우로 해석할 수 있다.

출력

총 수식 비용을 출력한다.

예제3

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