Maximize Tree Path Score

You are given a tree \(T\) with \(n\) vertices. Each vertex \(i\) has a weight \(a_i\) and each edge has a weight. In this tree, for any two vertices \(u\) and \(v\) there is a unique simple path \(P(u,v)\) (a path that does not visit any vertex more than once). The length of a path is defined as the sum of the weights of the edges on that path.

You are also given two sets \(S\) and \(G\). Initially, you must choose a vertex as the current vertex and add it to \(S\). Then you may perform a sequence of operations (possibly zero or more). In each operation, suppose your current vertex is \(u\); you can choose any vertex \(v\) (with \(v \neq u\)) and do the following:

• Update the current vertex to \(v\).
• Add vertex \(v\) to \(S\).
• Add the simple path \(P(u,v)\) to \(G\). (Note that even if a vertex or a path is added multiple times, \(S\) and \(G\) are sets, so duplicates are counted only once.)

After you finish all operations, your profit is defined as the product of:

1. The sum of the weights of the vertices in \(S\), and
2. The minimum length among all paths in \(G\). (If \(G\) is empty, its value is considered to be 0.)

Formally, if \(S\) is the set of vertices chosen in the process and if you performed at least one move so that \(G\) is nonempty, then the profit is

[ \text{Profit} = \Bigl( \sum_{v \in S} a_v \Bigr) \times \min_{\substack{\text{move } (u\to v)\ u\neq v}} ; \text{length}(P(u,v)). ]

Your task is to choose the starting vertex and the sequence of moves in order to maximize the profit. Note that you must perform at least one move.

Input constraints: Since the problem is NP‐hard in general, you may assume that \(n\) is small (for example, \(n \le 16\)).

inputFormat

The input is given as follows:

n
a1 a2 ... an
u1 v1 w1
...
un-1 vn-1 wn-1

The first line contains an integer \(n\) (number of vertices). The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the weight of each vertex. Each of the next \(n-1\) lines contains three integers \(u\), \(v\) and \(w\) indicating that there is an edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer, the maximum profit achievable.

sample

3
100 1 100
1 2 100
2 3 1

20200

</p>