9366: CCC '22 S5 - Good Influencers
Description
There are N (N≥2) students in a computer science class, with distinct student IDs ranging from 1 to N. There are N-1 friendships amongst the students, with the i-th being between students $A_i,B_i\ (A_i≠B_i,\ 1≤A_i≤N,\ 1≤B_i≤N)$. Each pair of students in the class are either friends or socially connected. A pair of students a and b are socially connected if there exists a set of students $m_1,m_2,…,m_k$ such that
- $a$ and $m_1$ are friends,
- $m_i$ and $m_{i+1}$ are friends (for 1≤i≤k−1), and
- $m_k$ and $b$ are friends.
Initially, each student i either intends to write the CCC (if $P_i$ is Y) or does not intend to write the CCC (if $P_i$ is N). Initially, at least one student intends to write the CCC, and at least one student does not intend to write the CCC.
The CCC has allocated some funds to pay some students to be influencers for the CCC. The CCC will repeatedly choose one student i who intends to write the CCC, pay them $C_i$ dollars, and ask them to deliver a seminar to all of their friends, and then all of their friends will intend to write the CCC.
Help the CCC determine the minimum cost required to have all of the students intend to write the CCC.
Input
The first line contains the integer $N\ (2 \leq N \leq 200,000)$.
The next $N-1$ lines each contain two space-separated integers, $A_i, B_i\ (1≤i≤N-1)$.
The next line contains $N$ characters, $P_1…P_N$, each of which is either Y or N.
The next line contains $N$ space-separated integers, $C_1…C_N$.
Output
Constraints
$1 \leq C_i \leq 1,000$
Sample 1 Input
4
1 2
2 3
3 4
YNYN
4 3 6 2
Sample 1 Output
6
Sample 2 Input
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
Sample 2 Output
6