树的难题
时间限制:10s 空间限制:128MB
题目描述
给出一个无根树。树有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
题目来源
没有写明来源