[Usaco2011 Jan]瓶颈
时间限制：10s 空间限制：259MB
题目描述
Farmer John有一张N个农场构成的网络(1 <= n="" <="100,000)" ，我们将农场标记为1n。="" 农场被n-1条单向道路连接，保证从任何一个农场可以到达1号农场。fj想让奶牛到1号农场集中="" （p.s.="" 至于要做什么我也不知道）。="" 对于每个农场i=""> 1都有一条单独的单向道路通往P_i，并且这个农场里有C_i只奶牛
（1 <= c_i="" <="1,000,000,000）。在每个单位时间里，这条道路允许不超过M_i" (0="" (1="" farmer="" john="" 想让所有的奶牛都集中在1号农场（农场容纳奶牛的数量是没有限制的）。="" 下面是奶牛集中到1号农场过程的规则：="" *="" 我们认为时间是离散的="" 任何奶牛都可以在一个单位时间里走过任意多条道路。但是，必须满足每条道路的上限m_i。="" 奶牛从来不会离开1号农场。="" 换句话说，每一个单位时间，每只奶牛可以选择下面行动之一：="" a)="" 留在当前的农场="" b)="" 经过一条或者多条道路，向1号农场移动。同样，需要满足每条道路的上限m_i。="" fj想知道有多少奶牛可以在某个特定的时刻到达1号农场。特别的，他有一张列着k="" 个时间t_i="" 的策略在这个时刻结束时最多能有多少奶牛到达1号农场。="" 考虑如下一个样例（树退化成链），列表里只有t_1="5一个时刻，奶牛如下分布："
输入格式
* 第1行：两个空格隔开的整数N和K * 第2到N行：第i行包含三个空格隔开的整数，表示农场i（不是i+1）的P_i，C_i，M_i * 第N+1到N+K行：第N+i行包含一个整数T_i
输出格式
* 第1K行：第i行包含一个整数，表示到T_i个单位时间为止能够到达1号农场奶牛的最多数量。
样例输入
4 1 1 1 5 2 12 7 3 12 3 5
样例输出
25
提示
没有写明提示
题目来源
没有写明来源