Ağac#4248
Hörmətli iştirakçı, yəqin ki, ağacın nə olduğunu bilirsiniz. Məlumat strukturlarında ağac, hər iki zirvə arasında yalnız bir yol olan qraf kimi təsvir edilir. Gəlin sadə bir məsələyə baxaq. Tutaq ki, ağacın zirvələri müəyyən çəkiyə malikdir və ağacın ümumi çəkisi onun bütün zirvələrinin çəkilərinin cəminə bərabərdir. Sizin vəzifəniz ağacı iki alt ağaca elə bölməkdir ki, onların çəkiləri arasındakı fərq minimal olsun.
Birinci sətir testlərin sayını göstərən ədədini ehtiva edir. Hər bir test üçün ilk sətir ağacdakı zirvələrin sayını göstərən (2 \leq N \leq 10000) ədədini ehtiva edir. Daha sonra, tam ədəd W_i (1 \leq W_i \leq 1000) verilir ki, bunlar -dən -ə qədər olan zirvələrin çəkiləridir.
Sonra N-1 sətir gəlir, hər biri ağacın kənarını təyin edən iki tam ədəd A_i və B_i (1 \leq A_i, B_i \leq N) ehtiva edir.
Hər bir test üçün bir tam ədəd çıxarın — çəkilərin ən kiçik fərqini.
Nümunə 1