Năng Lượng Về Phòng Gốc · canuc80k3526

Một tổ kiến có $N$ phòng nối với nhau bằng $N - 1$ đường hầm, tạo thành một cây. Phòng $1$ là phòng gần mặt đất nhất và được chọn làm gốc. Mỗi đường hầm có một độ dài dương; đi qua đường hầm đó tiêu tốn đúng số đơn vị năng lượng bằng độ dài của nó.

Ban đầu phòng $v$ có một con kiến mang $E_{v}$ đơn vị năng lượng. Mỗi con chỉ đi dọc đường duy nhất từ phòng hiện tại về phòng $1$ . Nó có thể đi qua một đường hầm khi năng lượng còn lại không nhỏ hơn độ dài hầm; sau đó năng lượng giảm đi đúng độ dài ấy. Hãy xác định, với từng con kiến, phòng gần gốc nhất mà nó có thể tới.

Input

Dòng đầu chứa số nguyên $N$ .
$N$ dòng tiếp theo; dòng thứ $v$ chứa năng lượng $E_{v}$ của con kiến ở phòng $v$ .
$N - 1$ dòng tiếp theo, mỗi dòng chứa $a, b, c$ , mô tả đường hầm nối $a$ với $b$ có độ dài $c$ .

Output

In $N$ dòng; dòng thứ $v$ là số phòng gần gốc nhất mà con kiến xuất phát ở $v$ có thể tới.

Constraints

$1 \leq N \leq 1 0^{5}$ .
$1 \leq E_{v} \leq 1 0^{5}$ .
$1 \leq a, b \leq N$ và $1 \leq c \leq 1 0^{4}$ .
Các đường hầm tạo thành một cây.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Con kiến ở phòng $4$ tốn $6$ năng lượng để tới phòng $2$ , còn lại $1$ nên không thể đi tiếp qua đường hầm dài $5$ . Con kiến ở phòng $5$ có đủ năng lượng cho cả quãng $5 \to 2 \to 1$ .

Ý tưởng: Gốc hóa cây tại phòng 1. Với mỗi phòng u và mức b, lưu up[u][b] là tổ tiên cách 2^b cạnh và cost[u][b] là tổng độ dài của đúng đoạn đường đó. Hai bảng được ghép từ hai nửa liên tiếp qua tổ tiên trung gian.
Ý tưởng: Với mỗi con kiến, xét các mức từ lớn xuống nhỏ. Nếu tổ tiên của cả khối tồn tại và chi phí khối không vượt năng lượng còn lại, nhận khối đó, trừ chi phí và chuyển lên tổ tiên tương ứng. Sau khi hết các mức, phòng hiện tại là phòng cao nhất có thể tới.
Chứng minh đúng: Theo quy nạp trên b, up[u][b] và cost[u][b] mô tả chính xác đường đi gồm 2^b cạnh từ u lên trên. Mọi trọng số đều dương nên nếu một khối vượt ngân sách thì không thể nhận cả khối, còn khi khối vừa ngân sách thì nhận nó luôn an toàn. Duyệt bit từ lớn xuống xây số cạnh lớn nhất có tổng chi phí không vượt năng lượng; mọi cạnh đã nhận nằm liên tiếp trên đường về gốc. Vì vậy không tồn tại tổ tiên cao hơn còn đạt được, và đỉnh cuối là đáp án.
Độ phức tạp: O(N log N) thời gian và O(N log N) bộ nhớ.
Lưu ý cài đặt: Hai lỗi trọng tâm cần tránh là: dùng điều kiện chi phí nhỏ hơn nghiêm ngặt năng lượng; và nhảy nhiều khối nhưng không trừ năng lượng đã tiêu.