GSHS 3 분할

경기도의 명소인 경기과학고등학교에는 $1$번부터 $N$번까지 번호가 매겨진 건물이 있고, 건물들은 $N-1$개의 양방향 도로로 연결되어 있습니다. 모든 건물이 서로 연결되어 있으므로 경기과학고등학교는 트리 구조입니다. 악당 동현이는 경기과학고등학교를 여러 조각으로 나눈 뒤 이곳을 지배할 계획을 세우고 있습니다.\n\n첫 번째 계획이 실패하자 동현이는 두 번째 계획을 쓰기로 했습니다. 이 계획에서 동현이는 도로 2개를 파괴해 경기과학고를 3개의 영역으로 나눕니다. 두 건물은 파괴되지 않은 도로만 거쳐 한 건물에서 다른 건물로 이동할 수 있으면 같은 영역에 속합니다.\n\n동현이는 학교에 숨겨 둔 스파이를 통해 $i$번 건물에 학생이 $A_i$명 있다는 사실을 알고 있습니다. 경기과학고를 세 영역으로 나눈 뒤, 각 영역의 결집도는 그 영역에 있는 학생 수로 정합니다. 세 영역의 결집도를 곱한 값을 지배력이라고 합니다.\n\n예를 들어 $N=7$이고 $A=[1, 3, 4, 0, 3, 6, 2]$인 경우를 생각해 봅시다.\n\n\n\n동현이가 $1$번과 $5$번 건물 사이의 도로, 그리고 $5$번과 $7$번 건물 사이의 도로를 파괴하면 경기과학고등학교는 아래 그림처럼 세 영역으로 나뉩니다.\n\n\n\n$1$번 건물을 포함한 영역의 결집도는 $1+4+0=5$입니다. $2$번 건물과 $6$번 건물을 포함한 영역의 결집도는 각각 $6$, $8$입니다. 따라서 이 경우의 지배력은 $5\\times 6\\times 8=240$입니다.\n\n경기과학고를 세 영역으로 나눠 동현이가 얻을 수 있는 지배력의 최댓값을 구하는 프로그램을 작성하세요.

첫째 줄에 경기과학고등학교 건물의 수 $N$이 주어집니다.\n\n둘째 줄에 각 건물의 학생 수 $A_1$, $A_2$, $\\cdots$, $A_N$이 공백으로 구분되어 주어집니다.\n\n셋째 줄부터 $N+1$번째 줄까지 $i+2$번째 줄에 정수 $U_i$, $V_i$가 공백으로 구분되어 주어집니다. 이는 $i$번째 도로가 $U_i$번 건물과 $V_i$번 건물을 양방향으로 연결함을 뜻합니다.

첫째 줄에 동현이가 경기과학고를 세 영역으로 나눠 얻을 수 있는 지배력의 최댓값을 출력합니다.

• $3 \\le N \\le 10^5$\n- $0 \\le A_i \\le 30$ $(1 \\le i \\le N)$\n- $1 \\le U_i < V_i \\le N$ $(1 \\le i \\le N-1)$\n- 경기과학고등학교의 구조는 트리입니다.