3236 - 皇宫看守
时间限制 : 1 秒
内存限制 : 128 MB
太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。
皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可以互相望见,宫内保卫森严,三步一岗,五步一哨,每个宫殿都要全天有人看守,在不同的宫殿安排看守所需的费用不同。
可是陆小凤手上的经费不足,但无论如何也要设法在每个宫殿都安置留守侍卫。
编程任务:帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。
输入
输入文件中数据表示一棵树,描述如下。
第一行n,表示树中节点的数目。
第二行至第n+1行,每行描述每个官殿节点信息,依次为:该宫殿节点标号i ,(0 < i ≤ n),在该宫殿安置侍卫所需的经费 k ,该边的子节点数m,接下来m个数,分别是这个节点的m个子节点的标号r_1,r_2...r_m。
对于一个n,(0 < n ≤ 1500)个节点的树,节点标号在1到n之间,且标号不重复。
输出
输出文件仅包含一个数,为所求最少的经费。
样例
输入
6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0
输出
25
来源
动规专题