C. Алёона ба мод

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Алёона хоолны дэглэм барихаар шийдсэн ба ой уруу явж алим цуглуулахаар болжээ. Гэнэт тэрээр нэгэн шидэт үндэстэй мод олсон ба уг модны үндэс нь $1$-р орой дээр байрласан байх бөгөөд орой, ирмэг болгон дээр нь ямар нэгэн тоо бичигдсэн байв.

Охин уг модны зарим оройнууд нь гунигтай байхыг анзаарсан ба иймд тэрээр тэдгээр оройнуудтай тоглохоор шийджээ. Хэрэв $v$-р оройны дэд модон дээр $dist(v, u) > a_{u}$ байх $u$-р орой оршин байвал бид $v$-р оройг гунигтай байна гэж үзнэ. Энд $a_{u}$ нь $u$-р орой дээр бичигдсэн тоог илэрхийлэх ба $dist(v, u)$ нь $v$-ээс $u$-р орой хүртэлх зам дээрх ирмэгүүд дээр бичигдсэн тоонуудын нийлбэрийг илэрхийлэх юм.

Модны навчнууд гэдэг нь нэг оройтой нэг ирмэгээр холбогдсон оройнуудыг хэлнэ. Хэрэв зөвхөн уг мод нь ганцхан оройноос тогтох буюу зөвхөн үндэстэй байвал модны үндэс нь навч болох юм.

Түүнчлэн Алёона уг модонд ямар ч гунигтай орой үлдээгүй болох хүртэл модны зарим навчнуудыг авч хаяхаар шийджээ. Тэгвэл Алёона хамгийн багадаа хэчнээн ширхэг навч авч хаях хэрэгтэй вэ?

Оролт

Эхний мөрөнд модны оройнуудын тоог илэрхийлэх бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг бүхэл тоонуудын дараалал $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) өгөгдөх ба энд $a_{i}$ нь $i$-р орой дээр бичигдсэн тоог илэрхийлэх юм.

Дараагийн $n - 1$ мөрөнд модны ирмэгүүдийг дүрсэлнэ: $i$-р мөр нь 2 бүхэл тоо $p_{i}$ болон $c_{i}$ $(1 ≤ p_{i} ≤ n$, $ - 10^{9} ≤ c_{i} ≤ 10^{9})$-аас тогтох ба энэ нь $i + 1$-р орой болон $p_{i}$-р оройг холбох өөр дээрээ $c_{i}$ гэсэн тоо бичигдсэн ирмэг оршин байгаа гэсэн үг юм.

Гаралт

Уг модонд ямар ч гунигтай орой үлдээгүй болох хүртэл Алёона-ын авч хаях хэрэгтэй навчнуудын хамгийн бага тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8
Гаралт
5

Тэмдэглэл

Дараах зурагт модноос навчнуудыг авч хаях нэгэн боломжит үйл явцыг дүрслэв:

Сэтгэгдлүүдийг ачааллаж байна...