14 · 树的完美染色

题目描述

给定一棵有 $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$ 的所有后代结点组成。

第一行包含一个整数 $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$ 为根的树，不存在环。

输出一个整数，表示将整棵树变为完美树的最小总代价。

输入 #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