P6615 Strawberry Strawberry

Little M likes strawberries very much. A strawberry can be abstracted as a tree $T$. I do not know why it works, but strawberries can even fly, so it should not be a big problem to abstract them as a tree.

Given a tree $T$, both vertices and edges have weights. A simple path is a path that does not pass through any vertex more than once. It can be proved that the simple path between two nodes $u$ and $v$ is unique; we denote it by $P(u,v)$. The length of a path is the sum of the weights of all edges on it. You have two sets $S$ and $G$. At the beginning, you must choose one node as the **current node** and add it to the set $S$. Then you may perform any number of operations. One operation is as follows: Suppose your **current node** is $u$. You may choose a node $v$ such that $v \neq u$, then update your **current node** to $v$, add node $v$ to the set $S$, and add the path $P(u,v)$ to the set $G$. After you finish all operations, the profit you get is: the minimum of (the sum of vertex weights of all nodes in $S$) $\times$ (the sum of lengths of all paths in $G$). If $G$ is empty, we consider the value of the second term to be $0$. Note that both $S$ and $G$ are **sets, not multisets**. This means that even if you add the same node to $S$ multiple times, it is counted only once when computing the vertex-weight sum. Find the maximum possible profit.

The first line contains an integer $n$. The next line contains $n$ integers $a_1,a_2 \ldots a_n$, representing the vertex weights of these $n$ nodes. The next $n - 1$ lines each contain three integers $u,v,w$, indicating that there is an edge of weight $w$ between $u$ and $v$.

Output one integer, the maximum profit.

This problem uses **bundled testdata**. | Subtask ID | $n$ | Special Property | Score | | :--------: | :-----------: | :--------------: | :---: | | 1 | $\leq 10$ | | 5 | | 2 | $\leq 100$ | | 13 | | 3 | $\leq 900$ | | 8 | | 4 | $\leq 214748$ | The tree is a chain. | 13 | | 5 | $\leq 214748$ | $a_i=0$ | 1 | | 6 | $\leq 214748$ | | 60 | For all data, it is guaranteed that $1 \leq n \leq 214748$, $0 \leq a_i \leq 10000$, and $1 \leq w \leq 10000$. --- #### Sample #1 Explanation The graph given in the first sample is as follows. [](https://imgchr.com/i/EWyWjg) Translated by ChatGPT 5