Bottleneck

Farmer John is gathering his cows. His farm is a network of $N$ fields numbered $1$ through $N$ ($1 \le N \le 100000$), connected by $N-1$ one-way paths that all eventually lead to field $1$. The fields and paths form a tree.

Every field $i$ other than field $1$ has exactly one outgoing one-way path to field $P_i$ ($1 \le P_i \le N$) and currently holds $C_i$ cows ($1 \le C_i \le 10^9$). During one unit of time, at most $M_i$ cows can move from field $i$ to field $P_i$ ($0 \le M_i \le 10^9$); that is, at most $M_i$ cows may traverse that path per unit of time.

Farmer John wants every cow to gather in field $1$ (which has no limit on how many cows it may hold). The rules are:

• Time passes in discrete units.
• A single cow may traverse several paths within the same unit of time. However, at most $M_i$ cows in total may leave field $i$ (traverse its outgoing path) during the same unit of time.
• Cows never move away from field $1$.

In other words, during each unit of time every cow chooses either to

1. stay in its current field, or
2. move one or more fields toward field $1$, as long as no path's bottleneck limit is violated.

Farmer John wants to know how many cows can reach field $1$ by certain times. He has a list of $K$ times $T_i$ ($1 \le K \le 10000$, $1 \le T_i \le 10^9$); for each $T_i$ he wants the maximum number of cows that can arrive at field $1$ by time $T_i$ under an optimal schedule.

For example, suppose the tree is a straight line, the cows are distributed as shown, and the only time of interest is $T_1 = 5$:

Field:     1---2---3---4      <-- field numbers
C_i:       0   1   12  12     <-- current number of cows
M_i:           5   8   3      <-- path limits (field 1 has no exit, so no limit)

The goal is to move cows to field $1$; one optimal progression is:

Tree:      1---2---3---4
t=0        0   1   12  12     <-- initial state
t=1        5   4   7   9
t=2        10  7   2   6
t=3        15  7   0   3
t=4        20  5   0   0
t=5        25  0   0   0

So the answer is $25$: all $25$ cows can reach field $1$ by time $t = 5$.

• Line $1$: two space-separated integers $N$ and $K$.
• The next $N - 1$ lines: line $i$ (for $i = 2, 3, \dots, N$) describes field $i$ with three space-separated integers $P_i$, $C_i$, and $M_i$.
• The next $K$ lines: each contains a single integer $T_i$.

• Output $K$ lines: line $i$ contains a single integer, the maximum number of cows that can arrive at field $1$ by time $T_i$.