There are \(N\) (\(N \ge 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\) and \(B_i\) (\(A_i \not= B_i\), \(1 \le A_i \le N\)
and \(1 \le B_i \le 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, \ldots, m_k\) such that

• \(a\) and \(m_1\) are friends,

• \(m_i\) and \(m_{i+1}\) are friends (for \(1 \leq i \leq 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.

\(N \ge 2\)
\(1 \le A_i \le N\)
\(1 \le B_i \le N\)
\(1 \leq i \leq k-1\)
\(1 \leq i \leq N-1\)

Marks

The following table shows how the available 15 marks are
distributed.

The first line contains the integer \(N\).

The next \(N-1\) lines each contain
two space-separated integers, \(A_i\)
and \(B_i\) (\(1 \leq i \leq N-1\)).

The next line contains \(N\)
characters, \(P_{1}\ldots P_{N}\), each
of which is either Y or
N.

The next line contains \(N\)
space-separated integers, \(C_{1}\ldots C_{N}\).

Output the minimum integer number of dollars required to have all of
the students to intend to write the CCC.

생성자가 기록되지 않았습니다.

출처 CCC 2022 Senior