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

ĐỘI QUÂN ĐỘC LẬP

Cấu trúc tổ chức của MathX là một cái cây gồm N nhân viên (đỉnh 1 là sếp tổng). Mỗi nhân
viên i có một chỉ số năng lực V[i]. Bạn cần chọn ra một đội ngũ sao cho không có hai nhân
viên nào là cấp trên trực tiếp của nhau (tức là không có hai đỉnh kề nhau trên cây được chọn)
để tổng năng lực là lớn nhất.

Dữ liệu vào

o Dòng 1: Số nguyên N (1 ≤ N ≤ 105).
o Dòng 2: N số nguyên V[i] (1 ≤ V[i] ≤ 109).
o N-1 dòng tiếp theo: Mỗi dòng gồm 2 số u, v mô tả quan hệ cấp trên - cấp dưới.

Kết quả: Tổng năng lực lớn nhất.

Ví dụ

INPUT                                OUTPUT                              GIẢI THÍCH
 3                                    15                                  Chọn nhân viên 2 và 3, bỏ
 1 5 10                                                                   nhân viên 1
 1 2
 1 3