树的难题

题目描述

给出一个无根树。树有N个点，边有权值。每个点都有颜色，是黑色、白色、
灰色这三种颜色之一，称为一棵三色树。
可爱的 Alice觉得，一个三色树为均衡的，当且仅当，树中不含有黑色结点
或者含有至多一个白色节点。然而，给出的三色树可能并不满足这个性质。 
所以，Alice打算删去若干条边使得形成的森林中每棵树都是均衡的，花费
的代价等于删去的边的权值之和。请你计算需要花费的代价最小是多少。 
注意，输入文件包含多组测试数据。

---

输入格式

 
第一行包含一个正整数 T，表示有 T组测试数据。接下来依次是 T组测试数
据。每组测试数据的第一行包含一个正整数 N。
第二行包含 N个 0、1、2之一的整数，依次表示点 1到点 N的颜色。其中，
0 表示黑色，1表示白色，2表示灰色。
接下来 N-1行，每行为三个整数ui、vi、c i，表示一条权值等于ci的边(ui, vi)。

---

输出格式

输出 T行，每行一个整数，依次表示每组测试数据的答案。

---

样例输入

 
1 
5 
0  1 1 1 0
1  2 5
1  3 3
5  2 5
2  4 16
 
 
 
 

---

样例输出

10 

---

提示

花费 10的代价删去边(1, 2)和边(2, 5)。
对于 100%的数据：1      ≤ N     ≤ 300 000   ，1 ≤ T  ≤ 5   ，0    ≤ ci<=10^9
 

---

题目来源

没有写明来源