Problem Description

Given a tree, node $i$ has a weight $c_i$. Some nodes are blue Y, and some nodes are white N. In each operation, you can choose a blue node and recolor all directly adjacent white nodes to blue. The cost of this operation is the weight of the chosen blue node.

Find the minimum total cost to recolor the entire tree to blue.

It is guaranteed that there is at least one white node and at least one blue node.

Input Format

The first line contains an integer $n$, the size of the tree.

The next $n-1$ lines each contain two integers $a_i$, $b_i$, meaning that $a_i$ and $b_i$ are directly connected.

The next line contains $n$ characters indicating the initial color of each node.

The next line contains $n$ integers indicating the weight of each node.

Output Format

One line containing the minimum total cost.

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

Hint

For $30\%$ of the testdata: $2 \le n \le 2000$, $1 \le c_i \le 1000$, and $a_i=i, b_i=i+1$.

For another $50\%$ of the testdata: $2 \le n \le 2000$, $1 \le c_i \le 1000$.

For $100\%$ of the testdata: $2 \le n \le 2 \times 10^5$, $1 \le c_i \le 1000$.

Translated by ChatGPT 5