408783: GYM103316 J Random Resources

Rake Mully has arrived on a new planet to collect a secret resource named hardtogetium. Hardtogetium is freely available on a location called the world tree, and Rake plans to traverse parts of the world tree and collect as much of this resource as he can.

Specifically, the world tree consists of $$$n$$$ hardtogetium mines, where the $$$i$$$th mine contains $$$w_i$$$ tons of hardtogetium. Furthermore, given any two mines, it is guaranteed that there exists a unique path between those two mines that Rake can travel along.

Rake has limited capacity, so he's decided to mine hardtogetium in the following way. Rake will randomly select two distinct vertices, $$$u, v$$$, and will collect all the hardtogetium from the mine with the maximum amount of hardtogetium on the path from $$$u$$$ to $$$v$$$, and he must consume hardtogetium equal to the amount in mine with the minimum hardtogetium on the path to power his mining apparatus. Specifically, given $$$u$$$ and $$$v$$$, he will collect $$$\max_x w_x - min_x w_x$$$ for all $$$x$$$ on the path from $$$u$$$ to $$$v$$$.

Given that he is equally likely to pick any possible $$$u, v$$$, what is the expected number of tons of hardtogetium that Rake will collect. This number can be expressed as a non-reducible fraction $$$\frac{p}{q}$$$, so output $$$pq^{-1} \pmod {10^9 + 7}$$$.

The first line consists of a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ giving the number of mines. The next line consists of $$$n$$$ integers where the $$$i$$$th integer $$$w_i$$$ gives the number of tons of hardtogetium on mine $$$i$$$. The next $$$n - 1$$$ lines consist of two integers $$$u_i, v_i$$$ $$$(1 \leq u_i, v_i \leq n)$$$, which indicates that there is an edge that Rake can travel across between $$$u_i$$$ and $$$v_i$$$.

Output the expected number of tons of hardtogetium that Rake will collect. This number can be expressed as a non-reducible fraction $$$\frac{p}{q}$$$, so output $$$pq^{-1} \pmod {10^9 + 7}$$$.

3
4 5 6
1 2
1 3

666666673

5
5 2 1 4 6
1 2
1 3
2 4
3 5

4

For the first input, Rake can expect to collect $$$\frac{6 - 4 + 6 - 4 + 5 - 4}{3}$$$ tons, which gives us $$$\frac{5}{3}$$$.