【例题2】结点覆盖

题目描述

给出一棵有根树，要求选出一些结点。若选中某个结点，则它本身、它的父亲结点和儿子结点被覆盖。选出第 $i$ 个结点需要一定的花费 $k_{i}$ ，求覆盖这棵树所需的最小花费。

第一行一个正整数 $n$ ，表示树中结点的数目。

第二行至第 $n+1$ 行，每行描述一个结点信息，依次为：该结点标号 $i$ ，选择该结点的花费 $k$ ，该结点的儿子数 $m$ ，接下来 $m$ 个数，分别是这个结点的 $m$ 个儿子的标号 $r_1$ ， $r_2$ ， $r_3$ ， $\cdots$ ， $r_m$ 。

对于一个 $n$ 个结点的树，结点标号在 $[1,n]$ ，且标号不重复。

一行整数，表示最小的花费。

对于 $100\%$ 的数据，满足 $1 < n < 1500$ 。

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0