树

题目描述

一棵 $n$ 个节点的树，每个点是黑色或者白色。每条边有边权。

设 $S$ 是黑色点的集合，$T$ 是白色点的集合。则树的价值是

$dis(u,v)$ 指的是树上 $u$ 到 $v$ 的简单路径包含的边的边权最大值。

简单路径指路径上的顶点都不相同的路径。

至多可以改变一个点的颜色，最大化树的价值。

大样例：sample.zip。

输入格式

输入包含 $n+1$ 行。

第一行输入一个正整数 $n$。

第二行输入 $n$ 个整数，第 $i$ 个整数 $c_i$ 表示节点 $i$ 的颜色，其中 $c_i=0,1$ 分别表示节点是白色/黑色。

接下来 $n-1$ 行，每行 $3$ 个正整数 $u,v,w$，表示连接节点 $u,v$ 的双向边，边权是 $w$。

输出格式

输出一个正整数，表示树的最大价值。

样例 1 输入

3
0 0 1
1 2 1
1 3 2

样例 1 输出

4

样例 2 输入

4
0 1 0 1
1 2 3
2 4 2
3 2 3

样例 2 输出

12

备注

对于所有的测试点，$0\le c_i\le1$，$1\le u,v\le n$，$1\le w\le10^9$。其中 $u\ne v$，保证 $(u,v,w)$ 形成一棵树。

• 对于测试点 $1\sim2$：$1\le n\le10$。
• 对于测试点 $3\sim4$：$1\le n\le10^2$。
• 对于测试点 $5\sim10$：$1\le n\le3\times10^3$。