İşçilərin iyerarxik strukturu
İllik səfər iclası zamanı Air Conditioning Machinery (ACM) şirkətində vaxt gəlib çatdı. Bütün işçilər bu tədbirdən məmnundurlar. Şirkət bir baş direktorun rəhbərlik etdiyi iyerarxik struktura malikdir. Hər bir işçi öz fəaliyyətinin nəticələrini iyerarxik struktura görə bir səviyyə yuxarıda olan menecerə bildirir. Hər bir işçinin e ilə əlaqəli olan əyləncə indeksi F(e) var ki, bu da onunla işləmək rahatlığını göstərir.
Alisa səfər qruplarını təşkil etməklə məşğuldur. Hər hansı bir işçinin meneceri qəzəblənəcək, əgər onun tabeliyində olanlardan biri səfər iclasına dəvət olunsa, amma o, dəvət olunmasa. Buna görə də Alisa qrupu elə təşkil etməlidir ki:
Baş direktor qrupa daxil olsun (bu aydındır).
Qrupda iştirak edən hər bir işçinin meneceri də qrupda iştirak etməlidir.
Alisa təşkil edə biləcəyi qrupun mümkün olan maksimum orta əyləncə indeksini hesablamaq istəyir. Ona kömək edə bilərsinizmi?
Baş direktor həmişə 1 nömrəli işçidir. Qrupun orta əyləncə indeksi qrupun bütün üzvlərinin əyləncə indekslərinin arifmetik ortasına bərabərdir.
Giriş verilənləri
Birinci sətir testlərin sayını t ehtiva edir.
Hər testin birinci sətiri işçilərin sayını N ehtiva edir.
Növbəti sətir boşluqla ayrılmış N ədəd ehtiva edir, burada i-ci ədəd i nömrəli işçinin əyləncə indeksini F(i) göstərir.
Növbəti N-1 sətirin hər biri iki ədəd a və b ehtiva edir ki, bu da b-nin a-ya hesabat verdiyini göstərir. (1 ≤ a, b ≤ N).
Məlumdur ki, 1 ≤ t ≤ 20, 1 ≤ N ≤ 50000, 0 ≤ F(i) ≤ 10000.
Çıxış verilənləri
Hər test üçün ayrı-ayrı sətirdə maksimum mümkün orta əyləncə indeksini üç ondalık dəqiqliklə yuvarlaqlaşdıraraq çıxarın.