Tutorial — Tỉa Nhánh

Vì thao tác xóa chỉ được thực hiện trên các đỉnh lá, việc xóa một đỉnh bất kỳ đòi hỏi toàn bộ cây con của đỉnh đó phải bị xóa hoàn toàn trước.

Một đỉnh $v$ làm quá tải một tổ tiên $u$ khi và chỉ khi khoảng cách lớn nhất từ một tổ tiên tới $v$ vượt quá $a_v$, và khi đó toàn bộ cây con tại $v$ bắt buộc phải bị loại bỏ.

Áp dụng thuật toán DFS từ gốc $1$ để duy trì giá trị khoảng cách lớn nhất từ tổ tiên theo công thức $d_v = \max(0LL, d_u + c)$; nếu $d_v > a_v$ thì dừng nhánh duyệt tại $v$, ngược lại tiếp tục duyệt và đếm số đỉnh được giữ lại.