Kənarların boyanması
Sizə n zirvədən ibarət T ağacı verilib. Ağacın zirvələri 1-dən n-ə qədər tam ədədlərlə nömrələnib. Müxtəlif rənglərdən ibarət bir dəstəni nəzərdən keçirək, rənglər 1-dən n - 1-ə qədər tam ədədlərlə nömrələnib. Hər rəngin bir dəyəri var. Sizə rənglərin dəyərlərinin ardıcıllığı cost[1]
, cost[2]
, ..., cost[n−1]
verilib. Sizin vəzifəniz hər bir kənarı fərqli rəngə boyamaqdır ki, hər hansı iki insident kənar fərqli rənglərə boyansın və kənarların üzərindəki rənglərin dəyərlərinin cəmi minimal olsun.
Giriş məlumatları
Birinci sətir testlərin sayı t-ni (1 ≤ t ≤ 16) ehtiva edir.
Hər bir test nümunəsinin birinci sətiri tam ədəd n-i (1 ≤ n ≤ 100) ehtiva edir. İkinci sətir n - 1 müsbət tam ədəd cost[1]
, cost[2]
, ..., cost[n−1]
(1 ≤ cost[color]
≤ 1000) ehtiva edir. Növbəti n - 1 sətirin hər biri ağacın T-nin növbəti kənarını göstərən iki ədəd u və v ehtiva edir.
Çıxış məlumatları
Hər bir test üçün ayrı sətirdə bir tam ədəd - ağacın ən ucuz uyğun kənar boyanmasının dəyərini çıxarın.