2012. [USACO Jan11]瓶颈

【题目描述】

$Farmer John$有一张$N$个农场构成的网络$(1 <= N <= 100,000)$，我们将农场标记为$1..N$。农场被$N-1$条单向道路连接，保证从任何一个农场可以到达$1$号农场。农场和道路形成一棵树。$FJ$想让奶牛到$1$号农场集中（P.S. 至于要做什么我也不知道）。 

对于每个农场$i > 1$都有一条单独的单向道路通往$P_i$，并且这个农场里有$C_i$只奶牛$（1 <= C_i <= 1,000,000,000）$。在每个单位时间里，这条道路允许不超过$M_i (0 <= M_i <= 1,000,000,000)$只奶牛从农场$i$走到农场$P_i (1 <= P_i <= N)。$ 

$Farmer John $想让所有的奶牛都集中在1号农场（农场容纳奶牛的数量是没有限制的）。 

下面是奶牛集中到1号农场过程的规则： 

* 我们认为时间是离散的 

* 任何奶牛都可以在一个单位时间里走过任意多条道路。但是，必须满足每条道路的上限$M_i$。 

* 奶牛从来不会离开1号农场。 

换句话说，每一个单位时间，每只奶牛可以选择下面行动之一： 

a) 留在当前的农场 

b) 经过一条或者多条道路，向1号农场移动。同样，需要满足每条道路的上限$M_i$。 

$FJ$想知道有多少奶牛可以在某个特定的时刻到达$1$号农场。特别的，他有一张列着$K (1 <= K <= 10,000) $个时间$T_i (1 <= T_i <= 1,000,000,000)$的单子，他想知道对于每个$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$

【输出格式】

* 第$1..K$行：第$i$行包含一个整数，表示到$T_i$个单位时间为止能够到达1号农场奶牛的最多数量。

【样例输入】

4 1

1 1 5

2 12 7

3 12 3

5

【样例输出】

25

【来源】

John Pardon, 2010