경험치

X 회사에는 직원이 $N$명 있다. 회사 조직은 엄격한 트리 구조이다. 맨 위에는 최고경영자(CEO)가 있고(트리의 루트), 그 아래에 직속 부하 직원이 몇 명 있다. 이 부하 직원에게도 각자 직속 부하 직원이 있으며, 이렇게 내려가다 보면 부하 직원이 없는 말단 직원(트리의 리프)에 닿는다.

직원에게는 1번부터 $N$번까지 번호가 붙어 있다. CEO는 1번이고, 나머지 번호는 조직 구조와 아무 관련이 없다. 직원마다 경험치가 있으며, $i$번 직원의 경험치는 음이 아닌 정수 $W_i$이다.

회사에는 진행할 단체 프로젝트가 많아서, 경영진은 모든 직원을 여러 팀으로 나누기로 했다. 팀은 다음 두 조건을 지켜야 한다.

• 각 팀은 적어도 한 명으로 이루어지고, 모든 직원은 정확히 한 팀에만 속한다.
• 각 팀은 상하 관계가 연속으로 이어지는 사람들로만 이루어진다. 직원 $j_1, j_2, j_3, j_4, \dots$의 모임은 $j_2$가 $j_1$의 직속 부하이고, $j_3$이 $j_2$의 직속 부하이고, $j_4$가 $j_3$의 직속 부하이고, 이런 식으로 이어질 때만 올바른 팀이다.

단체 프로젝트가 끝나면 그 프로젝트를 맡은 팀의 총 경험치가 $W_{\max} - W_{\min}$만큼 늘어난다. $W_{\max}$는 그 팀에 속한 직원 경험치의 최댓값이고, $W_{\min}$은 최솟값이다. 회사 전체의 경험치 증가량은 모든 팀의 증가량을 더한 값이다. 경영진은 위 두 조건을 지키면서 팀을 가장 좋게 짜서 회사 전체의 경험치 증가량을 최대로 만들려고 한다.

회사가 얻는 경험치 증가량의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 회사의 직원 수 $N$이 주어진다.

둘째 줄에 각 직원의 경험치 $W_1, W_2, \dots, W_N$이 공백으로 구분되어 주어진다. 모두 음이 아닌 정수이다.

다음 $N - 1$개 줄에는 두 정수 $u$와 $v$가 이 순서대로 공백으로 구분되어 주어진다. 이는 $v$번 직원이 $u$번 직원의 직속 부하라는 뜻이다.

회사가 얻는 총 경험치 증가량의 최댓값을 정수 하나로 출력한다.

• $1 \le N \le 100000$
• $0 \le W_i \le 10^9$

그림은 직원 7명으로 이루어진 조직도이다. 원 안의 수는 직원 번호이고, 옆의 빨간 수는 그 직원의 경험치이다. 총 경험치 증가량이 최대가 되는 구성 중 하나는 {1, 5, 3}, {6, 2, 4}, {7}이다. {1, 5}, {3}, {6, 2, 4}, {7}도 같은 최댓값을 준다.