Anton - strażnik#237
Anton jest strażnikiem odpowiedzialnym za obiektów o numerach od do . Istnieje również n-1 dróg, gdzie -ta droga łączy obiekty u_i i v_i i ma długość w_i. Z każdego obiektu można dotrzeć do obiektu .
Na początku Anton znajduje się w obiekcie .
Zdefiniujmy priorytet każdego obiektu jako minimalną liczbę dróg, które trzeba przebyć z tego obiektu do obiektu . Na przykład dla obiektu ta liczba wynosi ; dla wszystkich obiektów bezpośrednio połączonych z , wynosi , i tak dalej.
Anton musi odwiedzić wszystkie obiekty. Musi najpierw odwiedzić wszystkie obiekty, które mają priorytet , następnie te, które mają priorytet , i tak dalej. Jeśli istnieją obiekty o tym samym priorytecie, Anton może wybrać kolejność ich odwiedzania. Zauważ, że może odwiedzić każdy obiekt o priorytecie tylko po odwiedzeniu wszystkich obiektów o priorytecie k-1.
Znajdź minimalną odległość, jaką musi przebyć.
W pierwszej linii znajduje się liczba całkowita (1 \leq n \leq 10^6).
W drugiej linii znajduje się n-1 liczb całkowitych p_i, które wskazują, że istnieje droga z obiektu i+1 do obiektu p_i (1 \leq p_i \leq n).
W trzeciej linii znajduje się n-1 liczb całkowitych w_i, które są długościami dróg między obiektami i+1 i p_i (1 \leq w_i \leq 10^9).
Zagwarantowane jest, że można dotrzeć do wszystkich innych obiektów z obiektu .
Wyjście powinno zawierać pojedynczą liczbę całkowitą — odpowiedź na problem.
Przykład 1
Przykład 2
Przykład 3
( punkty): 1 \le n \le 10;
( punktów): 1 \le n \le 22;
( punktów): nie więcej niż obiektów ma ten sam priorytet;
( punktów): nie więcej niż obiektów ma ten sam priorytet;
( punktów): w_i = 1;
( punktów): 1 \le n \le 10^5;
( punktów): bez dodatkowych ograniczeń.