Ağacın qeyri-sabitliyi
Bir ağac N zirvəsi ilə verilir. Hər bir u zirvəsi üçün bir dəyər c_u təyin olunub. Kökü olan ağacın qeyri-sabitliyi aşağıdakı şəkildə müəyyən edilir:
Burada L_i ağacın kökünə görə i zirvəsinin səviyyəsini göstərir. Kök həmişə 0 səviyyəsindədir. Siz ağacda kökü elə seçməlisiniz ki, ağacın qeyri-sabitlik dəyəri minimum olsun.
Giriş verilənləri
Birinci sətir testlərin sayını T göstərir. Hər bir testin birinci sətiri ağacın zirvələrinin sayını N ehtiva edir. Növbəti sətir N tam ədədləri, boşluqla ayrılmış şəkildə, ehtiva edir, burada i-ci ədəd ağacın i-ci zirvəsinin dəyəridir. Sonrakı N-1 sətirin hər biri iki tam ədəd a və b (1 ≤ a, b ≤ N) ehtiva edir ki, bunlar a və b zirvələri arasında kənarı təsvir edir.
Məlumdur ki, 1 ≤ T ≤ 20, 1 ≤ N ≤ 20000, 1 ≤ c_i ≤ 1000.
Çıxış verilənləri
Çıxış məlumatları T sətirdən ibarətdir. Hər bir sətir müvafiq test üçün ağacın qeyri-sabitliyinin ən kiçik mümkün dəyərini göstərir.