31750번 - Split the GSHS 3 서브태스크

문제

경기도의 명소 경기과학고등학교에는 1ドル$부터 $N$까지의 번호가 매겨진 건물이 $N-1$개의 양방향 도로로 연결되어 있고, 모든 건물들은 연결되어 있습니다. 즉, 경기과학고등학교는 트리 구조입니다. 악당 동현이는 경기과학고등학교를 여러 조각으로 분열시킨 후 경기과학고등학교를 지배할 계획을 세우고 있습니다.

동현이가 계획한 첫 번째 계획의 실패로, 동현이는 자신의 두 번째 계획을 사용하기로 했습니다. 이 계획에서 동현이는 경기과학고에 있는 길 중 2ドル$개를 파괴해 경기과학고를 3ドル$개의 영역으로 나누고자 합니다. 두 건물이 같은 영역에 속해 있다는 것은 파괴되지 않은 도로들을 통해 한 건물에서 다른 건물로 이동할 수 있음을 뜻합니다.

동현이는 이미 경기과학고등학교에 숨겨놓은 스파이를 통해 $i$번 건물에는 학생이 $A_i$명임을 알고 있습니다. 경기과학고를 세 영역으로 나눈 뒤, 각 영역의 결집도를 해당 영역에 있는 학생의 수로 정의합니다. 또한 세 영역의 결집도의 곱을 지배력이라고 정의합니다.

예를 들어, 아래 그림과 같이 건물의 개수 $N=7$이고, 각 건물에 있는 학생의 수가 $A=[1, 3, 4, 0, 3, 6, 2]$인 경우를 생각해 봅시다.

동현이가 1ドル,ドル 5ドル$번 건물 사이의 길과 5ドル,ドル 7ドル$번 건물 사이의 길을 파괴하면 경기과학고등학교는 다음과 같이 세 영역으로 분할됩니다.

이때, 1ドル$번 건물이 포함된 영역의 결집도는 1ドル+4+0=5$이며, 2ドル$번 건물, 6ドル$번 건물이 포함된 영역의 결집도는 각각 6ドル,ドル 8ドル$입니다. 따라서 이 경우의 지배력은 5ドル\times 6\times 8=240$입니다.

동현이가 경기과학고를 세 영역으로 나눠 얻을 수 있는 지배력의 최댓값을 구하는 프로그램을 작성하세요.

입력

첫째 줄에 경기과학고등학교의 건물의 수를 나타내는 정수 $N$이 주어집니다.

둘째 줄에 각 건물에 있는 학생의 수 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 띄어쓰기를 사이에 두고 주어집니다.

셋째 줄부터 $N+1$번째 줄까지 $i+2$번째 줄에 두 개의 정수 $U_i,ドル $V_i$가 순서대로 띄어쓰기를 사이에 두고 주어집니다. 이는 $i$번째 도로가 $U_i$번 건물과 $V_i$번 건물을 양방향으로 연결함을 나타냅니다.

출력

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

제한

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

서브태스크

힌트