T562787 「2025 YAC Round 2」華鳥風月 II

「2025 YAC Round 2」F 题

四季映姬有一颗包含 $n$ 个节点的灵魂之树，每一个节点代表一个灵魂的状态，非黑即白。 四季映姬有两种操作如下： - 删除一个白节点，花费代价为 $0$。 - 将一个白节点变为黑节点，花费代价为 $1$。 四季映姬每一次操作只能执行其中一种操作。 现在，她想要进行若干次操作使得灵魂之树中 **剩余的节点全为黑色**，且这些剩余的黑节点 **依旧组成一颗树**。请计算最小花费。

第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示灵魂之树的节点数量。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$a_i = \{ 0, 1 \}$），其中若 $a_i=0$，表示节点 $i$ 的为白色；否则为黑色。 接下来的 $n-1$ 行，每行输入两个正整数 $u, v$（$1 \le u, v \le n$，$u \not = v$），代表存在一条连接节点 $u$ 和 $v$ 的边。 保证 $n - 1$ 条边不重复且构成一颗树。

输出一个整数表示答案。

### 样例解释 将节点 $2$ 变为黑色，花费代价为 $1$； 将节点 $3$ 和 $5$ 删除，花费代价为 $0$； 最后剩余节点 $1,2,4$，全为黑色且构成一棵树。花费总代价为 $1$。 可以证明没有更优的方案。