Охоронець Антон#237

Охоронець Антон

3 секунди

256 мегабайтів

Складна

Антон працює охоронцем. Він відповідає за $n$ об'єктів, які пронумеровані цілими числами від $1$ до $n$ . Також є $n - 1$ n-1 дорога. $i$ -та дорога з'єднує об'єкти $u_{i}$ u_i та $v_{i}$ v_i, а також має довжину $w_{i}$ w_i. З кожного об'єкту можна дістатися до об'єкта $1$ .

На початку Антон знаходиться в об'єкті $1$ .

Визначимо пріоритетність кожного об'єкта, як мінімальну кількість доріг, яку потрібно пройти від цього об'єкта до об'єкта $1$ . Наприклад, для об'єкта $1$ це число буде $0$ ; для всіх об'єктів, які напряму з'єднані з $1$ — це буде $1$ ; і так далі.

Антону потрібно зробити обхід всіх об'єктів. Йому потрібно спочатку відвідати усі об'єкти, які мають пріоритетність $1$ , потім, які мають пріоритетність $2$ , і так далі. Якщо є кілька об'єктів з однаковою пріоритетністю, то Антон може самостійно вибирати у якому порядку їх відвідувати. Зверніть увагу, що відвідувати будь-який об'єкт з пріоритетом $k$ він може лише, якщо відвідав усі об'єкти з пріоритетом $k - 1$ k-1.

Знайдіть мінімальну відстань, яку йому прийдеться пройти.

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \leq n \leq 10^6).

Другий рядок містить $n - 1$ n-1 цілих чисел $p_{i}$ p_i, які показують, що є дорога від об'єкта $i + 1$ i+1 до об'єкта $p_{i}$ p_i ( $1 \leq p_{i} \leq n$ 1 \leq p_i \leq n);

Третій рядок містить $n - 1$ n-1 цілих чисел $w_{i}$ w_i, які є довжинами доріг між об'єктами $i + 1$ i+1 та $p_{i}$ p_i ( $1 \leq w_{i} \leq 1 0^{9}$ 1 \leq w_i \leq 10^9).

Гарантується, що з об'єкта $1$ можна дійти до всіх інших об'єктів.

Вихідні дані

Виведіть одне ціле число — відповідь на задачу.

Приклади

Приклад 1

Приклад 2

Приклад 3

Оцінювання

( $4$ бали): $1 \leq n \leq 10$ 1 \le n \le 10;
( $5$ балів): $1 \leq n \leq 22$ 1 \le n \le 22;
( $13$ балів): не більше $6$ об'єктів мають однакову пріоритетність;
( $10$ балів): не більше $10$ об'єктів мають однакову пріоритетність;
( $15$ балів): $w_{i} = 1$ w_i = 1;
( $15$ балів): $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5;
( $38$ балів): без додаткових обмежень.