A6291. 保安站岗
编程题
普及+/提高
知识点
题目描述
五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。
已知整个地下超市的所有通道呈一棵树的结构；某些通道之间可以互相望见。总经理要求所有通道的每个端点（也就是树的每个结点）都要有人全天候看守。在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某条通道的一个端点上，那么他除了能看守住他所站的那个端点外，也能看到这条通道的另一个端点。所以一个保安可能同时看守多个端点，因此没有必要在每个通道的端点都安排保安。
你的任务是：在保证所有结点都被看守到的前提下，使安排保安的总费用最小。
已知整个地下超市的所有通道呈一棵树的结构；某些通道之间可以互相望见。总经理要求所有通道的每个端点（也就是树的每个结点）都要有人全天候看守。在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某条通道的一个端点上，那么他除了能看守住他所站的那个端点外，也能看到这条通道的另一个端点。所以一个保安可能同时看守多个端点，因此没有必要在每个通道的端点都安排保安。
你的任务是：在保证所有结点都被看守到的前提下，使安排保安的总费用最小。
输入格式
第 1 行：一个整数 $n$，表示树中结点的数目。
接下来第 2 行至第 $n+1$ 行，每行描述一个结点的信息，格式为：
> $i\ k\ m\ r_1\ r_2\ \dots\ r_m$
含义为：
- $i$：结点编号（$0 < i \le n$，编号不重复）；
- $k$：在该结点安置一个保安所需的费用（$1 \le k \le 10000$）；
- $m$：该结点的儿子个数；
- 接下来 $m$ 个数 $r_1, r_2, \dots, r_m$：该结点的 $m$ 个儿子的编号。
整棵树有 $n$ 个结点，结点编号在 $1$ 到 $n$ 之间。
接下来第 2 行至第 $n+1$ 行，每行描述一个结点的信息，格式为：
> $i\ k\ m\ r_1\ r_2\ \dots\ r_m$
含义为：
- $i$：结点编号（$0 < i \le n$，编号不重复）；
- $k$：在该结点安置一个保安所需的费用（$1 \le k \le 10000$）；
- $m$：该结点的儿子个数；
- 接下来 $m$ 个数 $r_1, r_2, \dots, r_m$：该结点的 $m$ 个儿子的编号。
整棵树有 $n$ 个结点，结点编号在 $1$ 到 $n$ 之间。
输出格式
输出一行一个整数，表示在能看守所有结点的前提下所需的最小总费用。
输入输出样例
输入 #1
6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0
输出 #1
25
说明/提示
## 说明/提示
样例中，选择在结点 2、3、4 安置保安，可以看守所有 6 个结点，且总费用为 $16 + 5 + 4 = 25$，是最小方案。
- 对于所有数据，$0 < n \le 1500$；
- 结点费用 $1 \le k \le 10000$。
样例中，选择在结点 2、3、4 安置保安，可以看守所有 6 个结点，且总费用为 $16 + 5 + 4 = 25$，是最小方案。
- 对于所有数据，$0 < n \le 1500$；
- 结点费用 $1 \le k \le 10000$。