# [USACO11JAN]瓶颈Bottleneck

## 题意翻译

WC正在召集奶牛,他的农场有一个包含 ***N*** 块农田的网络，编号为 **1 -- N** ，每个农场里有 $C_i$ 头牛。农场被 **N-1** 条 **单向** 边链接,（每个农场有通向$P_i$的路） 保证从任何点可以到达1号点。WC想让所有奶牛集中到1号农场。
**时间是离散的** 奶牛可以在1单位时间里走过任意多条道路，但是每条路有一个容纳上限 *$M_i$* 并且奶牛不会离开1号农场(农场没有容量上限)
### 每一个单位时间，奶牛可以选择如下几种行动
1. 留在当前的农场
2. 经过几条道路，向1号农场移动（需要满足$M_i$）
WC想要知道有多少牛可以在某个特定的时刻到达1号农场，
他有一张列着 ***K*** 个时间（分别为$T_i$)的单子
，他想知道在每个$T_i$, 采用最优策略在$T_i$结束最多能有多少牛到1号农场
### 数据范围如下：
$1 \le N \le 10^5$
$1 \le C_i \le 10^9$
$1 \le M_i \le 10^9$
$1 \le P_i \le N$
$1 \le K \le 10^4$
$1 \le T_i \le 10^9$
## **输入输出格式**
* 输入格式
*第一行：两个整数 N 和 K
*第2—N行，第i行描述一块农场及它的路 $P_i \;C_i\;M_i$
*第N+1 - N+K行， 第N+i 一个整数 $T_i$
* 输出格式
*每行一个答案对应$T_i$
感谢@ToBiChi 提供翻译

## 题目描述

Farmer John is gathering the cows. His farm contains a network of N (1 <= N <= 100,000) fields conveniently numbered 1..N and connected by N-1 unidirectional paths that eventually lead to field 1. The fields and paths form a tree.
Each field i > 1 has a single one-way, exiting path to field P\_i, and currently contains C\_i cows (1 <= C\_i <= 1,000,000,000). In each time unit, no more than M\_i (0 <= M\_i <= 1,000,000,000) cows can travel from field i to field P\_i (1 <= P\_i <= N) (i.e., only M\_i cows can traverse the path).
Farmer John wants all the cows to congregate in field 1 (which has no limit on the number of cows it may have). Rules are as follows:
\* Time is considered in discrete units.
\* Any given cow might traverse multiple paths in the same time unit. However, no more than M\_i total cows can leave field i (i.e., traverse its exit path) in the same time unit.
\* Cows never move \*away\* from field #1.
In other words, every time step, each cow has the choice either to
a) stay in its current field
b) move through one or more fields toward field #1, as long as the bottleneck constraints for each path are not violated
Farmer John wants to know how many cows can arrive in field 1 by certain times. In particular, he has a list of K (1 <= K <= 10,000) times T\_i (1 <= T\_i <= 1,000,000,000), and he wants to know, for each T\_i in the list, the maximum number of cows that can arrive at field 1 by T\_i if scheduled to optimize this quantity.
Consider an example where the tree is a straight line, and the T\_i list contains only T\_1=5, and cows are distibuted as shown:
```cpp
Locn: 1---2---3---4 <-- Pasture ID numbers
C_i: 0 1 12 12 <-- Current number of cows
M_i: 5 8 3 <-- Limits on path traversal; field 1 has no limit since it has no exit
The solution is as follows; the goal is to move cows to field 1:
```
Tree: 1---2---3---4
```cpp
t=0 0 1 12 12 <-- Initial state
t=1 5 4 7 9 <-- field 1 has cows from field 2 and 3 t=2 10 7 2 6
t=3 15 7 0 3
t=4 20 5 0 0
t=5 25 0 0 0
Thus, the answer is 25: all 25 cows can arrive at field 1 by time t=5.

## 输入输出格式

### 输入格式

\* Line 1: Two space-separated integers: N and K
\* Lines 2..N: Line i (not i+1) describes field i with three
space-separated integers: P\_i, C\_i, and M\_i
\* Lines N+1..N+K: Line N+i contains a single integer: T\_i

### 输出格式

\* Lines 1..K: Line i contains a single integer that is the maximum number of cows that can arrive at field 1 by time T\_i.

## 输入输出样例

### 输入样例 #1

```
4 1
1 1 5
2 12 7
3 12 3
5
```

### 输出样例 #1

```
25
```