Sparing w Programowaniu Politechnika Poznańska, 24.02.2007

Opis

Deweloper (firma budowlana) zaprojektował w mieście takie osiedle, że skrzyżowania połączone są w strukturę drzewa. Celem było uniemożliwienie zakłócania spokoju huliganom motoryzacyjnym przez usunięcie pętli, po których mogliby się ścigać. Tylko skrzyżowanie przy wjeździe na osiedle jest połączone z resztą miasta. Deweloper sprzedaje ziemię wzdłuż dróg pomiędzy sąsiednimi skrzyżowaniami. Agencja nieruchomości stworzyła księgę spodziewanego zysku (dodatniego, zerowego lub ujemnego), jaki można uzyskać z zakupu ziemi przy każdej drodze.

Potencjalni nabywcy chcą zmaksymalizować swój zysk, ale wolą kupić jeden połączony fragment terenu rozciągający się wzdłuż drogi łączącej dwa skrzyżowania (niekoniecznie sąsiadujące) osiedla. Twoim zadaniem jest napisanie programu, który wyznaczy maksymalny nieujemny zysk, jaki można uzyskać w ten sposób lub poda wartość 0, gdy nie można osiągnąć zysku.

Dla przykładu rozważmy następującą reprezentację osiedla, gdzie etykiety dróg reprezentują spodziewany zysk. W tym przypadku maksymalny nieujemny zysk wynosi 7 i może być osiągnięty przy zakupie ziemi wzdłuż drogi pomiędzy skrzyżowaniami #2 i #5.

Specyfikacja wejścia

W pierwszej linii wejścia podana będzie liczba N (1 ≤ N ≤ 50) określająca liczbę scenariuszy.

Każdy scenariusz składa się z kilku linii. Pierwsza zawiera liczbę skrzyżowań n (1 ≤ n ≤ 5*10⁵), włącznie ze skrzyżowaniem "wjazdowym" oznaczonym numerem 0. Po pierwszej linii nastąpi n-1 kolejnych, gdzie k-te skrzyżowanie jest opisane w k-tej linii parą liczb całkowitych x (0 ≤ x < k) oraz p (-1000 ≤ p ≤ 1000), oznaczających bezpośredni fragment drogi z x do k o spodziewanym zysku p.

Specyfikacja wyjścia

Wyjście będzie sekwencją linii, po jednej dla każdego scenariusza. Każda linia będzie zawierała maksymalną nieujemną wartość zysku lub zero, gdy nie można go osiągnąć.

Przykład

5
6
0 -1
1 3
0 2
1 1
1 4
6
0 2
0 1
0 2
0 1
1 1
5
0 1
1 -3
0 -2
1 -2
5
0 -1
1 -3
0 -2
1 -2
10
0 -1
0 -1
0 0
1 3
1 4
2 4
2 2
3 3
3 3

7
5
1
0
7