C. Минжний-Ангууч-0xFF

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

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

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

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

"Минж ид, мод аварна!" - Энэ бол Минжит толгодод болсон экологич нарын шуурхай уулзалтын уриа байлаа.

Дэлхий дээр байгаа минж нарын хэмжээ маш их болсон байна. Өдөр бүр тэдний тоо толгой олноор нэмэгдэх бөгөөд тэд хүн төрөлхтөн болоод байгальд ямар их хор хөнөөл учруулахыг мэдэхгүй байлаа. Агаар мандалд байгаа хүчилтөрөгчийн хэмжээ 17 хувиар буурч, дэлхийн гоц ухаантнууд энэ бол төгсгөл биш гэжээ.

50-иад оны дундуур зөвлөлтийн эрдэмтэд газар нутгаа аврахын тулд нэгэн нууц технологийг хөгжүүлж байв. Тэдний технологи "Минжний-Ангууч-0xFF" хэмээх нууцлаг нэртэй. Одоо хүн төрөлхтөн шинжлэх ухааны төлөө амьдардаг хэсэг хүмүүст итгэл найдвараа хүлээлгэжээ.

Загвар бэлэн, би түргэхэн туршилтаар туршиж үзэх хэрэгтэй.

Таньд минжээр дүүрсэн мод өгөгдсөн. Мод бол холбогдсон чиглэлгүй цикл агуулдаггүй граф юм. Мод $n$ оройноос бүрднэ, $i$-р орой $k_{i}$ минж агуулна.

"Минжний-Ангууч-0xFF" дараах дарааллаар ажиллана : ямар нэг $u$ оройд байж байхдаа $v$ оройд очдог, хэрэв ирмэгээр холбогдсон бол $v$ оройд байгаа яг нэг минжийг иднэ. Хэрэв $v$ оройд минж байхгүй бол тийшээ очих боломжгүй юм. "Минжний-Ангууч-0xFF" зүгээр зогсоод минж идээд байдаггүй. "Минжний-Ангууч-0xFF" байнга хөдөлж байдаг.

Яагаад "Минжний-Ангууч-0xFF" ингэж ажилладаг юм бэ? Хөгжүүлэгчид анх бүтээхдээ батерей байрлуулах зай гаргаагүй бөгөөд минж идээд түүнийгээ цэвэр энерги болгож ажилдаг юм.

Минжүүд болж буй үйл явдлаас болоод шоконд орж хаашаа ч хөдлөхгүй. "Минжний-Ангууч-0xFF" хувьд дээрх нөхцөл хангаж байвал аль ч чиглэлд хөдөлж болно.

Модны үндэс $s$ орой бөгөөд "Минжний-Ангууч-0xFF"-г эндээс туршилтыг эхлүүлэхээр болсон. Туршилт дууссаны дараа "Минжний-Ангууч-0xFF" буцаад үндэс дээр ирнэ, доороос дээш авчирч ирэх хүн байхгүй учраас.

"Минжний-Ангууч-0xFF" хамгийн ихдээ хэдэн минжийг идээд орой дээр буцаж ирэхийг ол.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоо - модны оройн тоо. Хоёрдох мөрөнд $n$ бүхэл тоо $k_{i}$ ($1 ≤ k_{i} ≤ 10^{5}$) - харгалзах орой дээр байгаа минжүүдийн тоо. Дараагийн $n - 1$ мөр модыг илэрийлнэ. Дараагийн мөрөнд хоёр бүхэл тоо өгөгдөх ба эдгээр хоёр тоонд харгалзах оройнууд холбогдсон байна.Оройнууд $1$-ээс $n$ хүртэл дугаарлагдсан. Сүүлийн мөрөнд $s$ бүхэл тоо - туршилтыг эхлэх оройн тоо ($1 ≤ s ≤ n$).

Гаралт

"Минжний-Ангууч-0xFF"-ын хамгийн ихдээ идэж болох минжийн тоо.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Б.Алтангэрэл

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

Оролт
5
1 3 1 3 2
2 5
3 4
4 5
1 5
4
Гаралт
6
Оролт
3
2 1 1
3 2
1 2
3
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...