Mô tả và yêu cầu

Mirko cảm thấy mệt mỏi với công việc hàng ngày của mình vì vậy anh quyết định
sống một cuộc sống đơn giản và chuyển đến một vùng nông thôn. Tuy nhiên, mùa
đông ở ngôi làng xa xôi anh ấy mới chuyển đến rất khắc nghiệt, vì vậy anh ta quyết
định tự mình đi chặt củi.
Hôm nay, anh ấy sẽ chặt chiếc cây đầu tiên của mình. Trước khi cắt, anh ta dán nhãn
các bộ phận của thân cây đủ nhỏ để vừa với lò sưởi và đo độ cứng của chúng. Mirko
là một lập trình viên, vì vậy anh ấy nhận thấy rằng các bộ phận và mối liên hệ giữa
chúng tạo thành biểu đồ cây.
Thiệt hại trên chiếc rìu của anh ta do cắt một kết nối trên thân cây b ằng tổng của độ
cứng tối đa trong hai thành phần được kết nối được tạo thành bằng cách cắt
kết nối. Mirko chỉ có một chiếc rìu, vì v ậy anh ấy muốn tổng sát thương càng nh ỏ
càng tốt. Anh ấy muốn biết Tổng thiệt hại tối thiểu đối với chiếc rìu, nếu anh ta cắt
toàn bộ thân cây thành các bộ phận nhỏ vừa với lò sưởi.

Dữ liệu vào

 Dòng đầu tiên chứa số nguyên n, số phần. Các phần được gắn nhãn bởi các số
nguyên từ 1 đến n.
 Dòng thứ hai chứa n số nguyên ti (1 ≤ ti ≤ 10^9 ). S ố ti là độ cứng của phần
có nhãn i.
 Mỗi dòng trong số n - 1 dòng sau chứa hai số nguyên x và y (1 ≤ x, y ≤ n) -
nhãn của các bộ phận là kết nối trực tiếp.

Dữ liệu ra

 Tạo ra tổng thiệt hại tối thiểu sau n - 1 lần cắt.

Giới hạn và chấm điểm

 Sub1: 5% test với 1<=n<=10
 Sub2: 5% test với thành phần i và i+1 được nối trực tiếp
 Sub3: 30% test n<=1000
 Sub4: 60% test với n<=10^5

Ví dụ

INPUT            OUTPUT
                                3                 8
                                1 2 3
                                1 2
                                2 3
                                4                 15
                                2 2 3 2
                                1 3
                                3 2
                                4 3


        Giải thích ví dụ 1: Có hai cách để cắt thân cây này. Đầu tiên anh ta có thể
         cắt kết nối (1, 2), gây ra 1 + 3 = 4 thiệt hại, và sau đó cắt kết nối (2, 3), gây
         ra thiệt hại 2 + 3 = 5. Tổng thiệt hại là 9 trong này trường hợp. Nếu không,
         trước tiên anh ta có thể cắt (2, 3), và sau đó (1, 2). Tổng thiệt hại trong trường
         hợp đó (2 + 3) + (1 + 2) = 8.