병목

농부 존이 소들을 한곳에 모으려고 합니다. 농장에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 목초지가 있고 ($1 \le N \le 100000$), 이들은 $N-1$개의 단방향 경로로 연결되어 결국 모두 $1$번 목초지로 이어집니다. 목초지와 경로는 하나의 트리를 이룹니다.

$1$번이 아닌 각 목초지 $i$에는 목초지 $P_i$로 나가는 단방향 경로가 정확히 하나 있으며 ($1 \le P_i \le N$), 현재 $C_i$마리의 소가 있습니다 ($1 \le C_i \le 10^9$). 한 단위 시간 동안 목초지 $i$에서 $P_i$로 이동할 수 있는 소는 최대 $M_i$마리입니다 ($0 \le M_i \le 10^9$). 즉 그 경로는 한 단위 시간에 최대 $M_i$마리만 통과할 수 있습니다.

존은 모든 소를 $1$번 목초지에 모으고 싶습니다 ($1$번 목초지가 담을 수 있는 소의 수에는 제한이 없습니다). 규칙은 다음과 같습니다.

• 시간은 이산적인 단위로 흐릅니다.
• 한 마리의 소는 같은 단위 시간에 여러 경로를 연달아 지날 수 있습니다. 다만 같은 단위 시간에 목초지 $i$를 떠나는(그 출구 경로를 지나는) 소는 모두 합쳐 $M_i$마리를 넘을 수 없습니다.
• 소는 결코 $1$번 목초지에서 멀어지는 방향으로 움직이지 않습니다.

정리하면, 매 단위 시간마다 각 소는 다음 중 하나를 선택합니다.

1. 지금 있는 목초지에 머무른다.
2. 각 경로의 병목 제약을 어기지 않는 한, $1$번 목초지 쪽으로 하나 이상의 목초지를 지나 이동한다.

존은 특정 시각까지 몇 마리의 소가 $1$번 목초지에 도착할 수 있는지 알고 싶습니다. $K$개의 시각 $T_i$가 주어질 때 ($1 \le K \le 10000$, $1 \le T_i \le 10^9$), 각 $T_i$에 대해 이동을 최적으로 계획했을 때 시각 $T_i$까지 $1$번 목초지에 도착할 수 있는 소의 최대 마리 수를 구하세요.

예를 들어 트리가 일직선이고, 소가 아래처럼 분포하며, 살펴볼 시각이 $T_1 = 5$ 하나뿐이라고 합시다.

위치:      1---2---3---4      <-- 목초지 번호
C_i:       0   1   12  12     <-- 현재 소의 수
M_i:           5   8   3      <-- 경로 통과 제한 (1번은 출구가 없어 제한 없음)

목표는 소를 $1$번으로 옮기는 것이며, 한 가지 최적 진행은 다음과 같습니다.

트리:      1---2---3---4
t=0        0   1   12  12     <-- 초기 상태
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

따라서 답은 $25$입니다. 즉 $25$마리 모두 시각 $t = 5$까지 $1$번 목초지에 도착할 수 있습니다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $K$.
• 다음 $N - 1$개의 줄: $i$번째 줄 ($i = 2, 3, \dots, N$) 에는 목초지 $i$를 설명하는 세 정수 $P_i$, $C_i$, $M_i$가 공백으로 구분되어 주어집니다.
• 그다음 $K$개의 줄: 각 줄에 정수 $T_i$가 하나씩 주어집니다.

• $K$개의 줄에 걸쳐, $i$번째 줄에는 시각 $T_i$까지 $1$번 목초지에 도착할 수 있는 소의 최대 마리 수를 출력합니다.