마요 제국

아시아 역사에는 마요(Mayo)라는 고대 제국이 있었다. 당대에 가장 강한 나라 중 하나였다. 처음에 제국은 도시 하나로만 이루어져 있었고, 그 도시가 곧 수도였다. 마요 사람들은 뛰어난 전사였으므로 이웃 나라를 침략해 영토를 넓혀 갔다.

이웃 나라를 정복할 때마다 마요는 가장 큰 도시 하나만 남기고 그 나라의 도시를 모두 파괴한 뒤, 살아남은 도시를 제국에 편입했다. 그리고 그 도시와 원래 마요에 있던 도시 하나를 잇는 도로를 놓아 제국의 모든 도시 사이를 오갈 수 있게 했다. 새로 편입한 도시가 충분히 크면 그 도시가 마요의 새 수도가 되었다.

마요에 속한 도시의 취약도는 그 도시에서 마요의 수도까지 가는 동안 지나야 하는 도로의 수다. 마요가 침략한 나라의 목록과 그때 놓은 도로의 정보가 주어진다.

도시를 하나씩 편입할 때마다 도시의 취약도 중 최댓값이 얼마인지 알고 싶다. 출력을 간단히 하려고, $i$번째 도시를 편입한 직후의 최대 취약도를 $v_i$라 할 때 $v_1 + v_2 + \dots + v_n$을 구한다.

입력은 여러 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 마요의 도시 수 $n$ ($1 \le n \le 100\,000$)이 주어진다. 도시는 마요에 편입된 순서대로 $1$번부터 $n$번까지 번호가 붙는다. 따라서 $1$번 도시가 마요의 첫 도시이자 처음 수도다.

이어지는 $n - 1$개의 줄 중 $i$번째 줄에는 두 정수 $j$와 $c$가 주어진다. $i + 1$번 도시를 편입할 때 $i + 1$번 도시와 $j$번 도시 사이에 도로를 놓았다는 뜻이고, $j$는 이미 마요에 속한 도시의 번호다. $c$가 0이 아니면 $i + 1$번 도시가 편입되면서 마요의 새 수도가 되었다는 뜻이며, $c$가 0이면 수도는 그대로다.

입력의 마지막 줄에는 0 하나만 주어진다.

각 테스트 케이스마다 문제에서 설명한 최대 취약도의 합을 한 줄에 출력한다.