问题2234--结点覆盖

2234: 结点覆盖

时间限制: 1 Sec  内存限制: 128 MB
提交: 2  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

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


输入

第一行一个正整数n,表示树中结点的数目。
第二行至第n+1行,每行描述一个结点信息,依次为:该结点标号i(1<=i<=n),选择该结点的花费ki,该结点的
儿子数mi,接下来mi个数,分别是这个结点的mi个儿子的标号r1,r2,r3,.....,rm.
对于一个n个节点的树,结点编号为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

提示

n<=500.

来源/分类


[提交] [状态]