After recruiting for months, you finally score a SWE intern position at Sunnyside Daycare. Unfortunately, you didn't really do your research, so when you show up for the summer, you realize you're actually gonna be babysitting (what were you thinking?).
Bored and unsure how to deal with children, you decide to screenmaxx them instead. You study the daycare layout and luckily, it's a tree (seems the Leetcode is paying off). Each room has at most one TV, each of which you have configured to display meaningless brainrot at some level $$$a[i]$$$.
To truly screenmaxx though, the babies need access to as many TVs as possible. If they can walk from one TV to another, the total brainrot value of the daycare (and your subsequent enjoyment) increases by the product of those two TVs.
Unfortunately, your senior SWE catches on. They aren't paid nearly enough to deal with it though, so they'll lock exactly one door for the rest of the day, minimizing the total brainrot value. Given the daycare layout and each TV's brainrot level, what will be the total brainrot value for the day?
The first line of input contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of rooms.
The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^2$$$) — the brainrot levels of the TVs.
Each of the next $$$n - 1$$$ lines contains two integers $$$u, v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — representing a door between rooms $$$u$$$ and $$$v$$$.
It is guaranteed that the given doors form a tree.
Print a single integer — the minimum possible total brainrot value after the senior SWE locks one door.
The brainrot value is the sum of $$$a_u \cdot a_v$$$ over all pairs of different rooms $$$u$$$ and $$$v$$$ that are connected.
5 1 2 0 3 4 1 2 2 3 1 4 4 5
11
