P8399 [CCC 2022 S5] Good Influencers

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.

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.

One line containing the minimum total cost.

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