A7071. 树的完美染色
编程题
普及+/提高
知识点
题目描述
给定一棵有 $N$ 个结点的有根树（结点从 $1$ 到 $N$ 编号，根结点编号为 $1$）。
每个结点有一种颜色，或者为黑色，或者为白色。
对于任意一个结点 $u$，记以 $u$ 为根的子树中：
- 黑色结点的数量为 $B(u)$；
- 白色结点的数量为 $W(u)$。
称以结点 $u$ 为根的子树是「好的」，如果满足
$$ |B(u) - W(u)| \le 1. $$
称整棵树是「完美树」，如果对于所有 $1 \le i \le N$，以结点 $i$ 为根的子树都是好的。
你可以进行如下操作任意次（包括 $0$ 次）：
- 选择任意一个结点 $i$（$1 \le i \le N$），将结点 $i$ 的颜色翻转：
- 若当前为黑色，则变为白色；
- 若当前为白色，则变为黑色。
- 进行一次这样的操作，代价为 $P_i$。
请你求出，将给定的树变为完美树的最小总代价。
**注** ：以结点 $i$ 为根的子树，由结点 $i$ 以及结点 $i$ 的所有后代结点组成。
每个结点有一种颜色，或者为黑色，或者为白色。
对于任意一个结点 $u$，记以 $u$ 为根的子树中：
- 黑色结点的数量为 $B(u)$；
- 白色结点的数量为 $W(u)$。
称以结点 $u$ 为根的子树是「好的」，如果满足
$$ |B(u) - W(u)| \le 1. $$
称整棵树是「完美树」，如果对于所有 $1 \le i \le N$，以结点 $i$ 为根的子树都是好的。
你可以进行如下操作任意次（包括 $0$ 次）：
- 选择任意一个结点 $i$（$1 \le i \le N$），将结点 $i$ 的颜色翻转：
- 若当前为黑色，则变为白色；
- 若当前为白色，则变为黑色。
- 进行一次这样的操作，代价为 $P_i$。
请你求出，将给定的树变为完美树的最小总代价。
**注** ：以结点 $i$ 为根的子树，由结点 $i$ 以及结点 $i$ 的所有后代结点组成。
输入格式
第一行包含一个整数 $N$（$1 \le N \le 10^5$），表示树的结点个数。
接下来共 $N$ 行，第 $i$ 行描述结点 $i$ 的信息，格式为：
$C_i\ P_i\ K_i\ \text{child}_{i,1}\ \text{child}_{i,2}\ \dots\ \text{child}_{i,K_i}$
含义如下：
- $C_i$：结点 $i$ 的初始颜色，$C_i = 0$ 表示白色，$C_i = 1$ 表示黑色；
- $P_i$：将结点 $i$ 的颜色翻转一次所需的代价，$1 \le P_i \le 10^4$；
- $K_i$：结点 $i$ 的孩子数量，$0 \le K_i \le N$；
- 接下来 $K_i$ 个整数为结点 $i$ 的所有孩子的编号。
保证所有编号都在 $1 \sim N$ 之间，且输入结构是一棵以 $1$ 为根的树，不存在环。
接下来共 $N$ 行，第 $i$ 行描述结点 $i$ 的信息，格式为：
$C_i\ P_i\ K_i\ \text{child}_{i,1}\ \text{child}_{i,2}\ \dots\ \text{child}_{i,K_i}$
含义如下：
- $C_i$：结点 $i$ 的初始颜色，$C_i = 0$ 表示白色，$C_i = 1$ 表示黑色；
- $P_i$：将结点 $i$ 的颜色翻转一次所需的代价，$1 \le P_i \le 10^4$；
- $K_i$：结点 $i$ 的孩子数量，$0 \le K_i \le N$；
- 接下来 $K_i$ 个整数为结点 $i$ 的所有孩子的编号。
保证所有编号都在 $1 \sim N$ 之间，且输入结构是一棵以 $1$ 为根的树，不存在环。
输出格式
输出一个整数，表示将整棵树变为完美树的最小总代价。
输入输出样例
输入 #1
10 1 100 3 2 3 4 0 20 1 7 0 5 2 5 6 0 8 1 10 0 7 0 0 2 0 1 1 2 8 9 0 15 0 0 13 0 1 8 0
输出 #1
15
说明/提示
## 样例说明
样例中，一种最优方案为：
- 将结点 $9$ 从白色翻转为黑色，代价 $13$；
- 将结点 $6$ 从白色翻转为黑色，代价 $2$。
总代价 $13 + 2 = 15$。此时对每个结点 $u$，其子树都满足 $|B(u) - W(u)| \le 1$，因此整棵树为完美树。
样例中，一种最优方案为：
- 将结点 $9$ 从白色翻转为黑色，代价 $13$；
- 将结点 $6$ 从白色翻转为黑色，代价 $2$。
总代价 $13 + 2 = 15$。此时对每个结点 $u$，其子树都满足 $|B(u) - W(u)| \le 1$，因此整棵树为完美树。