题目描述

4月17日,在白巳津川市的白蛇九十九神社的活动中,由于突然发生的地震导致“神器”掉落下来摔坏,新海翔在收拾“神器”的时候被割伤。后来在异世界来客——苏菲缇雅的说明下得知,“神器”被破坏导致另一个世界中的圣遗物(artifact)流落到了这个世界中,而那些拥有圣遗物的人叫做使用者(user),而新海翔就是一个user。之后新海翔在巨大的刺激下觉醒overload的能力将记忆送回过去,而回到过去将会产生一个新的“枝”,或者说“世界线”。

但是实际上新海翔拥有的圣遗物是白蛇九十九神社中供奉的“神器”——世界之眼,真正掌控overload的是nine。nine可以沟通并观测平行世界,从未来向过去传输记忆,将“枝”裁剪掉。nine知道新海翔从“神器”被破坏之后所有经过的“枝”,他将所有平行世界中产生分支的点和被裁剪掉的点称为时间节点。显而易见,这是一个树形结构。
DQAaYn.png
现在nine已经使用overload的能力裁剪新海翔所在的“枝”,并准备将他现在的记忆传输到一个新的时间节点。为了更好的将记忆传输到一个新的时间节点,nine现在想要知道,以“神器”被破坏作为最开始的时间节点(编号为1),新海翔现在已经到达的所有时间节点中,最晚的节点经过了多少天。(最晚的节点就是距离编号为1的节点最远的节点)


输入格式

第一行输入包括一个整数$n(1\leq n\leq 10^5)$表示包括开始的时间节点在内,一共有n个时间节点。

接下来第2到n行输入,第i行输入包括两个整数$v_i$,$d_i$($v_i \leq n,1\leq d_i\leq 100)$表示第i个节点的父亲节点是$v_i$,并且i与$v_i$之间距离$d_i$天。(注意:i从2开始,输入保证是一颗树)


输出格式

输出一行一个整数ans,表示最晚的节点经过的天数。


样例数据

输入

8
1 1
2 2
2 7
1 5
3 3
3 2
3 4

输出

8

备注

DQAJeg.png


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务