题目描述

学校里有 $n$ 个人，编号为 $1$ 到 $n$，其中 $1$ 号是校长。除校长外，每个人都恰好有一个直接上级，第 $i$ 个人的直接上级是 $p_i$。整个学校的上下级关系构成一棵以校长为根的树。

在时刻 $0$，校长得知了放假的消息。消息按如下方式传递：

• 逐个打电话： 每个已经得知消息的人，会给自己的直接下属一个接一个地打电话。同一时刻一个人只能打一个电话。
• 通话时长： 打给 $v$ 的电话持续 $t_v$ 分钟，挂断时 $v$ 才算得知消息。
• 同时传递： $v$ 得知消息后，会立刻开始给自己的直接下属打电话，与其他人的通话同时进行。

每个人可以自由决定给自己的直接下属打电话的顺序，且一个人打完一个电话后会立刻打下一个。

请你为所有人安排打电话的顺序，使所有人得知消息的时刻之和最小，并输出这个最小值。校长得知消息的时刻为 $0$，也计入总和。

输入格式

从文件 notify.in 中读入数据。

第一行一个整数 $n$，表示学校的人数。

接下来 $n-1$ 行，依次给出编号 $i=2,3,\dots,n$ 的人的信息。每行两个整数 $p_i,t_i$，分别表示第 $i$ 个人的直接上级，以及打给第 $i$ 个人的电话时长。

输出格式

输出到文件 notify.out 中。

输出一行一个整数，表示所有人得知消息的时刻之和的最小值。

样例1输入

5
1 2
1 1
1 1
4 1

样例1输出

9

样例1解释

校长有三个直接下属：$2$ 号（通话 $2$ 分钟）、$3$ 号（通话 $1$ 分钟）和 $4$ 号（通话 $1$ 分钟），其中 $4$ 号还有一个直接下属 $5$ 号（通话 $1$ 分钟）。

最优方案是校长依次打给 $4$ 号、$3$ 号、$2$ 号，三人分别在时刻 $1,2,4$ 得知消息。$4$ 号得知消息后立刻打给 $5$ 号，$5$ 号在时刻 $2$ 得知消息，总和为 $0+4+2+1+2=9$。

如果校长依次打给 $3$ 号、$4$ 号、$2$ 号，则总和为 $10$。

样例2输入

8
1 6
1 3
2 7
2 1
3 2
4 9
4 2

样例2输出

88

样例3

见选手下发文件夹中的 notify3.in 与 notify3.ans。

样例4

见选手下发文件夹中的 notify4.in 与 notify4.ans。

数据范围

对于所有测试数据，保证 $1 \le n \le 2 \times 10^5$，$1 \le p_i < i$，$1 \le t_i \le 10^6$。

本题共 $24$ 个测试点，采用捆绑测试。只有通过一个子任务内的全部测试点，才能获得该子任务的全部分数；否则该子任务得 $0$ 分。

子任务编号	测试点编号	分值	$n \le$	特殊性质
1	$1 \sim 4$	10	8	无
2	$5 \sim 7$	5	$2 \times 10^5$	A
3	$8 \sim 10$	15		B
4	$11 \sim 13$			C
5	$14 \sim 16$		2000	无
6	$17 \sim 24$	40	$2 \times 10^5$

特殊性质 A：每个人至多有一个直接下属，即对于 $2 \le i \le n$，有 $p_i=i-1$。

特殊性质 B：所有人的直接上级都是校长，即对于 $2 \le i \le n$，有 $p_i=1$。

特殊性质 C：所有 $t_i$ 相等。