P9716 [EC Final 2022] Coloring

给定 $n$ 个元素，编号从 $1$ 到 $n$。元素 $i$ 的值为 $w_i$，颜色为 $c_i$。每个元素还有一个指针 $a_i$ 指向另一个元素。 最初，元素 $s$ 的颜色为 $1$，而所有其他元素的颜色都为 $0$。更正式地说，对于所有 $i\neq s$ $(1 \le i \le n)$，有 $c_s=1$ 和 $c_i=0$。 你可以任意多次执行以下操作： - 以代价 $p_i$ 将 $c_i\leftarrow c_{a_i}$。 你的得分等于所有颜色为 $1$ 的元素值的总和减去操作的总代价。 找出你能够获得的最大可能得分。

无

无

(There won’t be extra line breakers in the actual test cases.) In the first sample, you can successively perform the following operations: - Assign $c_2\leftarrow c_{a_2}$ at a cost of $p_2$, then $c=[1,1,0]$; - Assign $c_1\leftarrow c_{a_1}$ at a cost of $p_1$, then $c=[0,1,0]$; - Assign $c_3\leftarrow c_{a_3}$ at a cost of $p_3$, then $c=[0,1,1]$; - Assign $c_2\leftarrow c_{a_2}$ at a cost of $p_2$, then $c=[0,0,1]$. After the operations, only the color of element $3$ is $1$, so your score is equal to $w_3-(p_2+p_1+p_3+p_2)=1$. It can be shown that it is impossible to obtain a score greater than $1$.