우수 마을

N개의 마을로 이루어진 나라가 있다. 마을에는 1번부터 N번까지 번호가 붙어 있다. 이 나라의 마을과 길은 트리 구조를 이룬다. 즉, 마을과 마을을 직접 잇는 방향 없는 길이 N - 1개 있고, 어떤 마을에서도 다른 모든 마을로 길을 따라 이동할 수 있다. 두 마을 사이에 직접 연결된 길이 있을 때 두 마을은 인접하다고 한다.

주민들의 성취감을 높이기 위해 N개의 마을 중 일부를 우수 마을로 선정하려고 한다. 선정은 다음 조건을 모두 만족해야 한다.

1. 선정된 우수 마을의 주민 수 합이 최대가 되어야 한다.
2. 인접한 두 마을을 모두 우수 마을로 선정할 수 없다.
3. 우수 마을로 선정되지 않은 마을은 적어도 하나의 우수 마을과 인접해야 한다.

각 마을의 주민 수와 마을 사이의 길 정보가 주어질 때, 조건을 만족하도록 우수 마을을 선정했을 때의 최대 주민 수 합을 구하는 프로그램을 작성하시오.

첫째 줄에 정수 N이 주어진다. (1 <= N <= 10,000)

둘째 줄에는 1번 마을부터 N번 마을까지의 주민 수를 나타내는 N개의 자연수가 공백으로 구분되어 주어진다. 각 마을의 주민 수는 10,000 이하이다.

셋째 줄부터 N - 1개의 줄에는 서로 인접한 두 마을의 번호가 공백으로 구분되어 주어진다.

선정된 우수 마을의 주민 수 합의 최댓값을 출력한다.