#P3459. Bomb

    ID: 2659 传统题 4000ms 512MiB 尝试: 36 已通过: 7 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理二分答案图论二分图建模树算法点分治点分祖先维护距离辅助点压缩边二分查找Dinic当前弧优化CF2600

Bomb

Bomb

题目描述

SS 国在一个由 nn 个区域组成的试验区进行核试验。区域间有 n−1n-1 条双向道路,任意两个区域都能相互到达。每条道路有给定的通过时间。

以引爆区域为根看这棵树,除根以外的叶子都是观测点。科学家起初在非叶子区域。每个观测点有容量上限,所有观测点的总容量至少等于科学家总数。

所有科学家都可以同时出发。为每位科学家选择一个观测点,使每个观测点的人数不超过容量。求使所有科学家都能到达各自观测点的最短时间。

输入格式

第一行包含一个正整数 nn。区域编号为 1,…,n1,\dots,n。

接下来 nn 行,第 ii 行描述区域 ii。行首是子节点数 aia_i,接下来有 aia_i 对整数 bi,j,ci,jb_{i,j},c_{i,j}。bi,jb_{i,j} 是第 jj 个子节点的编号,ci,jc_{i,j} 是两者之间道路的通过时间。

行末有一个整数 tit_i。当 ai>0a_i>0 时,tit_i 表示区域 ii 起初的科学家人数。当 ai=0a_i=0 时,tit_i 表示该叶子的容量。

输出格式

输出一个整数,表示最短时间。

样例 #1

4
2 2 5 3 3 2
1 4 2 3
0 2
0 3
3

数据范围

1≤n≤100001\le n\le 10000,0≤ci,j,ti≤1000000\le c_{i,j},t_i\le 100000。题源说明测试采用随机数据,树的深度较小。