Ağac kəsənlərin kəndləri#11033
Midqardda n kənd var və bu kəndlər yollar şəbəkəsi ilə bir-birinə bağlıdır. Midqardda n - 1 yol mövcuddur və bu yollar vasitəsilə istənilən kənddən digərinə çatmaq mümkündür. Başqa sözlə, bu yollar şəbəkəsi bir ağac strukturunu təşkil edir. Kənd nömrəsi 1 paytaxtdır. Midqardlılar çoxlu ağac əldə edir və onlardan gəmilər tikirlər. İndi Midqardın hökmdarı bir il ərzində böyük bir donanma qurmaq və yeni torpaqlar və resurslar fəth etmək istəyir. Bunun üçün o, aşağıdakı strategiyanı tətbiq etməyi qərara alıb:
Bəzi kəndlərə valilər göndərmək. Lakin, valinin göndərildiyi kənddən paytaxta qədər olan sadə yolda başqa bir kənd olmamalıdır ki, ora da vali göndərilib. Qeyd edək ki, paytaxta bir vali göndərmək olar, amma bu halda başqa heç bir kəndə vali göndərmək olmaz.
v kəndindəki valiyə, sadə yolda paytaxta qədər olan kəndlərdən v kəndi olan bütün kəndlər tabe edilir. O cümlədən, valiyə v kəndi də tabe edilir.
Hər kənd üçün a[i] - əgər kənd heç bir valiyə tabe deyilsə, bir il ərzində bu kəndin tikəcəyi gəmilərin sayı məlumdur.
Əgər v kəndində vali varsa, o, aşağıdakı kimi hərəkət edir:
O, özünə tabe olan v ilə qonşu olan kəndlərin alt qüməsini W seçir. Bu kəndlərdə böyük gəmiqayırma emalatxanaları qurur. Hər kənd üçün məlumdur ki, əgər orada emalatxana qurulsa, bu kəndə b[i] digər kənddən ağac tədarük edilməlidir və bu emalatxana bir il ərzində c[i] gəmi istehsal edəcək.
İndi o, özünə tabe olan qalan kəndlərdən dəqiq Σ b[u] (u ∈ W) kənd seçməlidir ki, emalatxanalara ağac tədarük etsinlər. Hər birinin hansı konkret emalatxanaya ağac tədarük edəcəyi o qədər də vacib deyil.
Emalatxana qurulan i kəndi bir il ərzində c[i] gəmi tikəcək.
Ağac tədarükü ilə məşğul olan kənd gəmi tikməyəcək.
Onun tabeçiliyində olan digər kəndlər isə bir il ərzində sanki heç bir valiyə tabe deyillərmiş kimi eyni sayda gəmi tikəcəklər. Yəni, i kəndi bir il ərzində a[i] gəmi tikəcək.
Hökmdar istənilən sayda vali göndərə bilər. Valilər optimal şəkildə hərəkət edərsə, bütün kəndlərin bir il ərzində cəmi tikə biləcəyi maksimum gəmi sayını müəyyən edin.
Birinci sətirdə bir tam ədəd t (1 ≤ t ≤ 5000) - testlərin sayı verilir. Sonra t testlər gəlir.
Hər test bir tam ədəd n (1 ≤ n ≤ 5000) - Midqardda kəndlərin sayından başlayır.
Sonrakı n sətirdə üç tam ədəd a[i], b[i] və c[i] (1 ≤ a[i], c[i] ≤ 10^9, 1 ≤ b[i] ≤ n) - əgər kənd heç bir valiyə tabe deyilsə, bir il ərzində bu kəndin tikəcəyi gəmi sayı, əgər orada emalatxana qurulsa, bu kəndə ağac tədarük etməli olan kəndlərin sayı və əgər orada emalatxana qurulsa, bir il ərzində bu kəndin tikəcəyi gəmi sayı verilir.
Sonrakı n - 1 sətirdə Midqarddakı yolların təsvirləri verilir. Hər sətirdə iki tam ədəd v[i], u[i] - yolla birləşdirilmiş kəndlərin nömrələri verilir. Yollar şəbəkəsinin ağac əmələ gətirdiyi təmin edilir.
Bütün testlərdə n cəmi 5000-i keçməyəcəyi təmin edilir.
Hər test üçün bir tam ədəd çıxarın - valilərin düzgün paylanması ilə bütün kəndlərin bir il ərzində cəmi tikə biləcəyi maksimum gəmi sayı.
Nümunə 1