样例下载

【题目描述】

一棵圣诞树包含 N 个结点，编号为 1 ~ N。每个结点上挂着一盏灯，每盏灯有一种颜色，颜色只可能是红、绿、蓝三种之一。每条树边有一个长度。

小明同学对树的美观有着自己的看法。他认为，如果一棵树中没有红色灯，或者最多挂着一盏绿色灯，则这棵树是美观的，否则，这棵树就是不美观的。

所以当小明看到圣诞树的时候，他会根据自己的想法来判断这棵树是否美观。

如果他认为圣诞树是不美观的，他就会去除圣诞树中的一些树边，使得得到的每棵树都是美观的。

问：他需要去掉的边的总长度最少是多少？

多组数据。

【输入格式】

第一行：一个整数 T，表示数据组数。

对于每组数据：

• 第一行：一个整数 N。
• 第二行：N 个字符，只可能包含 R, G, B 三种字符，字符间以单个空格隔开，其中第 i 个字符表示编号为 i 的点挂着的灯的颜色，R, G, B 依次表示红色、绿色、蓝色。
• 接下来 N-1行：每行包含三个整数 x, y, z 表示点 x 与点 y 之间有一条长度为 z 的树边。

【输出格式】

共 T 行，每组数据的答案占一行。

【样例输入】

1
5
R G G G R
1 2 3
1 3 2
2 4 6
5 2 4

【样例输出】

7

【样例解释】

【数据范围】

100% 的数据：$1 ≤ T ≤ 5, 1 ≤ N ≤ 3×10^5, 1 ≤ x, y ≤ N, 0 ≤ z ≤ 10^9$