#P2458. [SDOI2006] 保安站岗
[SDOI2006] 保安站岗
题目描述
五一来临,某地下超市为了便于疏通和指挥密集的人员和车辆,以免造成超市内的混乱和拥挤,准备临时从外单位调用部分保安来维持交通秩序。
已知整个地下超市的所有通道呈一棵树的形状;某些通道之间可以互相望见。总经理要求所有通道的每个端点(树的顶点)都要有人全天候看守,在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某个通道的其中一个端点,那么他除了能看守住他所站的那个端点,也能看到这个通道的另一个端点,所以一个保安可能同时能看守住多个端点(树的结点),因此没有必要在每个通道的端点都安排保安。
编程任务:
请你帮助超市经理策划安排,在能看守全部通道端点的前提下,使得花费的经费最少。
输入格式
第 行 ,表示树中结点的数目。
第 行至第 行,每行描述每个通道端点的信息,依次为:该结点标号 (),在该结点安置保安所需的经费 (),该边的儿子数 ,接下来 个数,分别是这个节点的 个儿子的标号 。
对于一个 ()个结点的树,结点标号在 到 之间,且标号不重复。
输出格式
输出一行一个整数,表示最少的经费。
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
提示
样例解释
在结点 安置 个保安能看守所有的 个结点,需要的经费最小:。