უმოკლესი გზა

დროის ლიმიტი: 4 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: CodeFest 2021


მოცემულია n წვეროიანი მიუმართავი ხე. i-ურ წვეროს მინიჭებული აქვს ნატურალური რიცხვი xi. ნებისმიერ ორ L და R წვეროს შორის მანძილი გამოითვლება შემდეგნაირად:

(L-დან R-მდე გზაზე არსებული xi-ების ნამრავლი) / (L-დან R-მდე გზაზე არსებული  წვეროების რაოდენობა)

თქვენი მიზანია, იპოვოთ უმოკლესი შესაძლო გზის სიგრძე და გამოიტანოთ უკვეცი წილადის სახით.

შემომავალი მონაცემები: პირველ სტრიქონზე შემოდის ერთი რიცხვი n (1≤n≤106). შემდეგ  n-1 სტრიქონზე შემოდის ორ-ორი რიცხვი Ai და Bi (1≤Ai,Bi≤n) - წიბოების აღწერა. ბოლო n სტრიქონზე კი შემოდის xi (1≤xi≤109)-ები. 

გამომავალი მონაცემები: გამომავალი მონაცემების ერთადერთ ხაზზე უნდა გამოიტანოთ ამოცანის პასუხი ფორმატით P/Q (სადაც P და Q თანამარტივი რიცხვებია).




მაგალითები

შესატანი მონაცემები
2 1 2 3 4 დაკოპირება
გამოსატანი მონაცემები
3/1 დაკოპირება
შესატანი მონაცემები
5 1 2 2 4 1 3 5 2 2 1 1 1 3 დაკოპირება
გამოსატანი მონაცემები
1/2 დაკოპირება