408306: GYM103091 F Star City

After a difficult fiscal year, MTL is raising donation money from Stanford Alumni. He's starting with the alumni who live in Star City. Star City consists of $$$n$$$ houses, numbered $$$1$$$ to $$$n$$$, which are connected by $$$n-1$$$ two-way roads. Every house can be reached from every other house with some series of roads. And there is at most $$$1$$$ house with more than $$$2$$$ roads leaving it.

MTL will start driving from house $$$x$$$ and stop at house $$$y$$$ ($$$y$$$ does not need to be different from $$$x$$$). At each house, MTL asks the alumni to make a donation offer. Alumni like to contribute equally, so at the end of MTL's drive, each house will pay the same amount as the smallest offer made. Help MTL find a route that raises the most money!

The first line contains the integer $$$n$$$ ($$$1\leq n\leq 10^5$$$).

The second line contains $$$n$$$ space-separated integers, representing how much the alumni at the $$$i^{th}$$$ house offers to donate. All donations are from $$$1$$$ to $$$10^9$$$ dollars.

The next $$$n-1$$$ lines contain two space-separated integers $$$a$$$ and $$$b$$$, representing that a road connects $$$a$$$ and $$$b$$$. $$$a$$$ and $$$b$$$ will be within 1 and $$$n$$$.

Your output should consist of two lines.

On the first line, output the maximum amount of donation money MTL can raise.

On the second line, output two space-separated integers $$$x$$$ and $$$y$$$ so that the route from $$$x$$$ to $$$y$$$ makes the most money. If there are multiple solutions, output the one with the smallest $$$x$$$; if there are multiple with the same smallest $$$x$$$, give the solution with the smallest $$$y$$$.

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

9
4 5

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

12
1 3