D. Запасы воды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Крот Аркадий построил у себя в огороде систему подземных бункеров на случай внезапного нападения орлов. Система состоит из $$$n$$$ бункеров, соединенных $$$n-1$$$ тоннелями; все бункеры находятся на разной глубине: чем меньше номер, тем ближе к поверхности земли бункер. Бункер с номером $$$1$$$ находится у самой поверхности земли, а любой другой бункер соединен тоннелем ровно с одним бункером выше.

В каждом бункере, кроме всего прочего, есть некоторый запас воды, сейчас в бункере $$$i$$$ находится $$$l_i$$$ литров воды. Аркадий хочет сделать так, чтобы во всех бункерах было поровну воды. Для этого он может в любой момент времени перелить из любого бункера $$$a$$$ в любой другой бункер $$$b$$$ любое количество воды, но только если бункеры $$$a$$$ и $$$b$$$ соединены тоннелем и бункер $$$a$$$ находится выше бункера $$$b$$$.

Аркадий скоро осознал, что не всегда возможно распределить воду поровну, поэтому он разрешил себе доливать в любой бункер воду, принесенную из дома. Определите, какое минимальное количество воды нужно принести Аркадию из дома, чтобы можно было равномерно распределить воду по бункерам.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество бункеров.

Вторая строка содержит $$$n - 1$$$ целое число $$$p_2$$$, $$$p_3$$$, ..., $$$p_n$$$ ($$$1 \le p_i \lt i$$$), где $$$p_i$$$ означает, что бункер $$$i$$$ соединен тоннелем с бункером $$$p_i$$$, лежащим выше.

Третья строка содержит $$$n$$$ целых чисел $$$l_1$$$, $$$l_2$$$, ..., $$$l_n$$$ ($$$0 \le l_i \le 10^6$$$) — текущий объем воды в каждом из бункеров.

Выходные данные

Выведите одно число — минимальный объем воды, которую нужно принести Аркадию из дома, чтобы распределить воду поровну между всеми бункерами.

Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-6}$$$.

Формально, пусть ваш ответ равен $$$a$$$, а ответ жюри равен $$$b$$$. Ваш ответ будет зачтен, если и только если $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Система оценки

В тестах общей стоимостью $$$20$$$ баллов выполняются дополнительные ограничения $$$n \le 10$$$, $$$l_i \le 10$$$.

В тестах общей стоимостью $$$40$$$ баллов выполняется дополнительное ограничение $$$n \le 1000$$$.

В тестах общей стоимостью не менее $$$30$$$ баллов выполняется дополнительное условие $$$p_i = i - 1$$$.

Примеры
Входные данные
5
1 2 3 4
1 2 3 4 5
Выходные данные
10.00000000000000000000
Входные данные
3
1 2
1 2 1
Выходные данные
0.50000000000000000000
Входные данные
4
1 1 3
1 3 4 1
Выходные данные
3.00000000000000000000
Примечание

В первом примере можно долить $$$4$$$ литра воды в первый бункер, $$$3$$$ литра воды во второй, $$$2$$$ литра воды в третий бункер и $$$1$$$ литр в четвертый. Тогда во всех бункерах будет по $$$5$$$ литров воды, а всего нужно будет долить $$$10$$$ литров.

Во втором примере нужно перелить $$$0.5$$$ литра воды из второго бункера в третий и долить $$$0.5$$$ литра в первый бункер. Тогда в каждом бункере будет по $$$1.5$$$ литра воды, а долить всего придется $$$0.5$$$ литра.

В третьем примере нужно перелить один литр из третьего бункера в четвертый, а затем долить один литр воды в четвертый бункер и два литра воды в первый бункер.