草莓 Strawberry

小 M 很喜欢草莓。 草莓可以抽象为一棵树 $T$。我也不知道为什么可以，但草莓甚至可以飞，抽象成一棵树想必问题也不大吧。

给定一棵树 $T$，点和边均有权值。 一条简单路径是一条不重复经过任意一个点的路径。可以证明，两个节点 $u$ 和 $v$ 之间的简单路径是唯一的，我们将其记为 $P(u,v)$。一条路径的长度是它所包含的所有边的权值和。 你有两个集合 $S$ 和 $G$。 在一开始，你必须选择一个点作为 **当前点** 并且将其加入集合 $S$。接下来可以进行任意次操作，一次操作的形式如下： 假设你的 **当前点** 为 $u$，你可以选择一个节点 $v$，使得 $v \neq u$，然后将你的 **当前点** 更新为 $v$，并且将点 $v$ 加入集合 $S$，将路径 $P(u,v)$ 加入集合 $G$。 在你进行完所有操作之后，你得到的收益为 $S$ 中所有点的点权和 $\times$ $G$ 中所有路径的长度的最小值。如果 $G$ 为空，我们认为第二项的值为 $0$。 注意 $S$ 和 $G$ 都是 **不可重集**，这意味着，即使你多次将某个点加入集合 $S$，最终在计算点权时，也只会被计算一次。 求得到的收益的最大值。

第一行一个整数 $n$。 接下来一行 $n$ 个整数 $a_1,a_2 \ldots a_n$，表示这 $n$ 个节点的点权。 接下来 $n - 1$ 行，每行三个整数 $u,v,w$，表示 $u$ 到 $v$ 有一条权值为 $w$ 的边。

输出一个整数，所求最大收益。

6
1 4 2 8 5 7
1 2 3
4 1 2
1 5 1
2 3 4
3 6 1

198

本题采用 **捆绑测试**。 | 子任务编号 | $n$ | 特殊性质 | 分值 | | :--------: | :-----------: | :--------------: | :--: | | 1 | $\leq 10$ | | 5 | | 2 | $\leq 100$ | | 13 | | 3 | $\leq 900$ | | 8 | | 4 | $\leq 214748$ | 树的形态是一条链 | 13 | | 5 | $\leq 214748$ | $a_i=0$ | 1 | | 6 | $\leq 214748$ | | 60 | 对于所有数据，保证 $1 \leq n \leq 214748, 0 \leq a_i \leq 10000$，$1 \leq w \leq 10000$。 --- #### 样例 #1 解释 第一组样例给定的图如下。 [](https://imgchr.com/i/EWyWjg)