დროის ლიმიტი: 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 დაკოპირება