Split the GSHS 3

Gyeonggi Science High School, a well-known landmark in Gyeonggi-do, has buildings numbered 1 through $N$. The buildings are connected by $N-1$ two-way roads, and every building can reach every other building, so the campus is a tree. The villain Donghyun plans to split Gyeonggi Science High School into several pieces and then rule it.\n\nAfter his first plan failed, Donghyun decided to use a second plan. In this plan, he destroys 2 of the roads to divide the school into 3 regions. Two buildings belong to the same region if one can reach the other using only roads that were not destroyed.\n\nThrough a spy he hid at the school, Donghyun knows that building $i$ has $A_i$ students. After the school is divided into three regions, the cohesion of each region is the number of students in that region. The dominance is the product of the cohesions of the three regions.\n\nFor example, take $N=7$ and $A=[1, 3, 4, 0, 3, 6, 2]$.\n\n\n\nDonghyun destroys the road between buildings 1 and 5 and the road between buildings 5 and 7. The school is then divided into three regions as shown below.\n\n\n\nThe cohesion of the region containing building 1 is $1+4+0=5$. The cohesions of the regions containing building 2 and building 6 are 6 and 8. So the dominance in this case is $5\times 6\times 8=240$.\n\nWrite a program that finds the maximum dominance Donghyun can get by dividing Gyeonggi Science High School into three regions.

The first line contains the number of buildings $N$.\n\nThe second line contains the number of students in each building, $A_1$, $A_2$, $\\cdots$, $A_N$, separated by spaces.\n\nFrom line 3 to line $N+1$, line $i+2$ contains two integers $U_i$ and $V_i$ separated by a space. This means the $i$-th road connects building $U_i$ and building $V_i$ in both directions.

Print one line containing the maximum dominance Donghyun can get by dividing Gyeonggi Science High School into three regions.

• $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- The structure of Gyeonggi Science High School is a tree.