406897: GYM102606 D Decay of Signals

When ECNU was first built, there were $$$n$$$ buildings, but only $$$n-1$$$ roads connecting them, due to limited budgets. I'm sure those who are proficient in graph theory will figure out that there would be exactly one path between any two buildings. Yes, that's true. And back then, ECNUers did not have so much population and so much traffic going around like nowadays, so they didn't think that one day it would be a problem.

At least not until, Cuber QQ, who was an old professor studying communication and signal processing, raised his concern and decided to deal with it by building a communication system in the campus, although some archaeologists believe that's not true — the main reason why he did this in the first place was he would rather stay in the lab with his cat rather than exhaustively ride a bicycle around the campus only to send a short message.

In particular, he built $$$n$$$ signal amplification stations, with amplification ratio $$$a_1, a_2, \ldots, a_n$$$, one in each building, and buried $$$n-1$$$ cables, one under each road, each connecting two amplifiers. When a signal was sent from one building $$$u$$$ to another building $$$v$$$, it would go in the shorted path. The initial strength of signal was $$$1$$$, then multiplied by the amplification ratio $$$a_u$$$, decayed along the cables and amplified by intermediate stations, until passing the amplifier at $$$v$$$ at the receiving end.

Formally, the strength of a signal sent by $$$u$$$, and received by $$$v$$$ is,

$$$$$$\frac{a_{p_1} a_{p_2} \cdots a_{p_m}}{m}$$$$$$

where $$$p_1, p_2, \ldots, p_m$$$ is the shorted path from $$$u$$$ to $$$v$$$. $$$m$$$ is at least $$$1$$$, and $$$p_1 = u$$$, $$$p_m = v$$$.

After many years, Quber CC, who is Cuber QQ is grand-grand-child, is officially a freshman at ECNU. When he looked into this faded history, he couldn't help wondering whether the system works at all. He is especially interested in finding out how bad the system can be, i.e., he wants to find two buildings $$$u$$$ and $$$v$$$, such that the signal sent from $$$u$$$ to $$$v$$$ would have the smallest strength. To this end, he immersed himself in the library and collected all the information needed.

TL;DR, given an undirected tree with values on node, find the path with minimal "product of values divided by the length of path".

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of buildings in the campus.

Each of the following $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$) — the $$$i$$$-th road in the campus.

The $$$i$$$-th of the following $$$n$$$ lines contains one integer $$$a_i$$$ ($$$0\le a_i\le 10^9$$$) — the amplification ratio of the amplifier built in the $$$i$$$-th building.

The only line of output is the minimal answer in the form of a completely reduced fraction "$$$x/y$$$", where $$$x$$$ and $$$y$$$ are relatively prime integers.

2
1 2
1
2

1/1

3
1 2
1 3
2
2
2

2/1

3
1 2
1 3
0
1
2

0/1