3018. 皇宫看守
时间限制：1000 MS 内存限制：64 MB
题目描述
## 题目描述 太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。 皇宫各个宫殿的分布，呈一棵树的形状，宫殿可视为树中结点，两个宫殿之间如果存在道路直接相连，则该道路视为树中的一条边。 已知，在一个宫殿镇守的守卫不仅能够观察到本宫殿的状况，还能观察到与该宫殿直接存在道路相连的其他宫殿的状况。 大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。 可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。 帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。 ## 输入格式 输入中数据描述一棵树，描述如下： 第一行 $n$，表示树中结点的数目。 第二行至第 $n+1$ 行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号 $i$，在该宫殿安置侍卫所需的经费 $k$，该结点的子结点数 $m$，接下来 $m$ 个数，分别是这个结点的 $m$ 个子结点的标号$r1,r2,\dots,rm$。 对于一个 $n$个结点的树，结点标号在 $1$ 到 $n$ 之间，且标号不重复。 ## 输出格式 输出一个整数，表示最少的经费。 ## 输入 ```in1 6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0 ``` ## 输出 ```out1 25 ``` ## 提示 在$2、3、4$结点安排护卫，可以观察到全部宫殿，所需经费最少，为 $16 + 5 + 4 = 25$。