3804: 树(第六轮02)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：2
题目描述
一棵n个节点的树，每个点是黑色或者白色。每条边有边权。
设s是黑色点的集合， T是白色点的集合。则树的价值是Σu∈s Σv∈T dis(u, v)。 dis(u, v)指的是树上u到v 的简单路径包含的边的边权最大值。
简单路径指路径上的顶点都不相同的路径。
至多可以改变一个点的颜色，最大化树的价值。
大样例：sample.zip
输入
输入包含n + 1行。
第一行输入一个正整数n。
第二行输入n个整数，第i个整数ci 表示节点i的颜色，其中ci = 0,1分别表示节点是白色/黑色。
接下来n − 1行，每行3个正整数u, v, w，表示连接节点u, v 的双向边，边权是w。
输出
输出一个正整数，表示树的最大价值。
样例输入 复制
3
0 0 1
1 2 1
1 3 2样例输出 复制
4提示
【样例 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 ≤ ci ≤ 1,1 ≤ u, v ≤ n, 1 ≤ w ≤ 109 。其中u ≠ v，保证(u, v, w)2T 形成一 棵树。
- 对于测试点1 ∼ 2： 1 ≤ n ≤ 10。
- 对于测试点3 ∼ 4： 1 ≤ n ≤ 10^2 。
- 对于测试点5 ∼ 10： 1 ≤ n ≤ 3 × 10^3 。