10245: 「一本通 5.2 例 5」皇宫看守

内存限制:512 MB 时间限制:1.000 S 提交:0 解决:0
评测方式:文本比较 命题人:

题目描述

太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。 皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状,某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。 可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。 帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。 ![Picture1](http://miao.su/images/2018/07/09/aaaabba2.png)

输入

输入中数据描述一棵树,描述如下: 第一行 $n$,表示树中结点的数目。 第二行至第 $n+1$ 行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号 $i\ (0

输出

输出最少的经费

样例输入 复制

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

提示


数据范围:对于 $100\%$ 的数据,$0 \lt n\le 1500$。