题目描述

给定一棵树，点 $i$ 的点权是 $c_i$，上面有的点是蓝点 Y ，有的点是白点 N 。每次操作可以选定一个蓝点，将和这个蓝点直接相连的白点染成蓝色，代价是选定的蓝点的点权。

求将整个树染成蓝色的最小代价。

数据保证存在至少一个白点和至少一个蓝点。

输入格式

第一行一个整数 $n$ 表示树的大小。

接下来 $n-1$ 行每行两个整数 $a_i$,$b_i$，表示 $a_i$ 和 $b_i$ 直接相连。

接下来一行 $n$ 个字符表示每个点初始颜色。

接下来一行 $n$ 个整数表示每个点的点权。

输出格式

一行，表示最小花费。

4
1 2
2 3
3 4
YNYN
4 3 6 2

6

15
1 5
5 2
2 15
15 4
2 10
8 3
3 1
1 6
11 6
12 6
11 9
11 14
12 7
13 7
NNYYYNYYNNNNNNN
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

6

提示

对于 $30\%$ 的数据：$2\le n\le 2000,1\le c_i\le1000$，且 $a_i=i,b_i=i+1$ 。

对于另外 $50\%$ 的数据：$2\le n\le 2000,1\le c_i\le1000$ 。

对于 $100\%$ 的数据：$2\le n\le 2\times10^5,1\le c_i\le1000$。