Network

Mr. X is a network administrator, though the network structure is pretty complicated, in this problem, we just simply think of it as a tree. So we can think there are $~n~$ network nodes, and between them, there are $~n-1~$ edges, each edge connects two nodes, and have a transfer speed $~Speed_i~$.

According to the definition of the tree structure, we know that there is a unique path between any two nodes $~u~$ and $~v~$, when node $~u~$ want to send some messages to $~v~$ over the network, the messages will be transmitted along this simple path, and the total transmission speed is determind by the speed of the slowest edge of the path, while the speed of other edge doesn't matter, so we can define the 'waste speed' of path $Path(u, v)$ as $Waste(u, v) = max(Speed_i) - min(Speed_i)$.

There are some resource nodes in the network, and others are user nodes, for every user node $~u~$, we can define it's 'maximum waste resource node'

$$MWRN(u) = argmax_{v \in resource\_node}(Waste(u, v))$$

And we use $~min(Waste(u, MWRN(u)))~$ as 'network evaluation value' to evaluate a network structure, the worse we think the network structure is. If there is no user node, the value will be zero, the higher this value is.

Now, Mr. X knows that the campany wants to turn a user node into a resource node, but he didn't know which one will be changed. In order to prepare for the worst situation, he wants to know, if the company choose the worst node to change, how worse the network structure will be. Which means you need to give the maximum value of the 'network evaluation value' among all possible situations.

The first line contains one integer $~n(1 \leq n \leq 10^5)~$

The second line contains $~n~$ integer, the $~i_{th}~$ integer show the node type for the $i_{th}$ node, $~0~$ for user node and $~1~$ for resource node.

Then follow $~n-1~$ lines, each line contains three integers $~u, v, t~$, means there is a edge connects the $~u_{th}~$ node and the $~v_{th}~$ node, and the transfer speed is $~t(1 \leq t \leq 10^9)~$.

One line contains two integers $~a~$ and $~b~$, which means if the company choose the $~a_{th}~$ node, the situation will be the worst, and in this case, the \emph{`network evaluation value'} is $~b~$. If there are multiple solutions, output one with smallest $~a~$.

10 
0 0 0 0 0 0 1 0 0 0 
2 1 10 
3 1 7 
4 1 3 
5 2 18 
6 4 5 
7 4 18 
8 7 19 
9 2 6 
10 7 20

5 16

the data guarantee that there is at least one user node.
the arguments of the maxima (abbreviated argmax) are the points of the domain of some function at which the function values are maximized.

2019中山大学程序设计竞赛（重现赛）