#P3459. Bomb
Bomb
Bomb
题目描述
国在一个由 个区域组成的试验区进行核试验。区域间有 条双向道路,任意两个区域都能相互到达。每条道路有给定的通过时间。
以引爆区域为根看这棵树,除根以外的叶子都是观测点。科学家起初在非叶子区域。每个观测点有容量上限,所有观测点的总容量至少等于科学家总数。
所有科学家都可以同时出发。为每位科学家选择一个观测点,使每个观测点的人数不超过容量。求使所有科学家都能到达各自观测点的最短时间。
输入格式
第一行包含一个正整数 。区域编号为 。
接下来 行,第 行描述区域 。行首是子节点数 ,接下来有 对整数 。 是第 个子节点的编号, 是两者之间道路的通过时间。
行末有一个整数 。当 时, 表示区域 起初的科学家人数。当 时, 表示该叶子的容量。
输出格式
输出一个整数,表示最短时间。
样例 #1
4
2 2 5 3 3 2
1 4 2 3
0 2
0 3
3
数据范围
,。题源说明测试采用随机数据,树的深度较小。