Minimum Cost to Color the Tree Blue

You are given a tree with n nodes. Each node i has an associated weight c_i and an initial color: blue (denoted by 'Y') or white (denoted by 'N'). Initially, there is at least one blue node and at least one white node.

An operation is defined as follows: choose a blue node and convert every white node that is directly adjacent (i.e. connected by an edge) to blue. The cost of the operation is equal to the weight c of the chosen blue node. Note that after an operation, the newly painted nodes become blue and can later be used to perform operations.

Your task is to determine the minimum total cost required to turn every node in the tree blue.

Hint: One way to solve this problem is to simulate a multi‐source expansion (similar to Prim's algorithm) starting from the initially blue nodes. For every white node, the cost to paint it blue is the weight of the blue neighbor that performs the operation. When a white node is painted blue, it in turn can be used to paint its own white adjacent nodes at a cost equal to its weight. The objective is to choose the best sequence of such operations so that the total cost is minimized.

Formally, if the tree is described by its set of edges, then when a blue node u is used to convert an adjacent white node v, the cost incurred is

\( c_u \).

Using a suitable algorithm (for example, a multi‐source Prim’s algorithm), you can compute the minimum cost required.

inputFormat

The input is given as follows:

 n
 s
 c1 c2 ... cn
 u1 v1
 u2 v2
 ...
 u(n-1) v(n-1)

Where:

• n is the number of nodes in the tree.
• s is a string of length n consisting of characters 'Y' or 'N', representing the initial color of each node (1-indexed). 'Y' indicates a blue node and 'N' indicates a white node.
• c1, c2, ..., cn are the positive integer weights for each node.
• Each of the next n-1 lines contains two integers u and v, representing an undirected edge between nodes u and v.

outputFormat

Output a single integer representing the minimum total cost required to turn all nodes blue.

sample

4
YNNY
3 2 5 7
1 2
2 3
3 4

5