Tutorial — Truy Tìm Nguồn Sóng

Trạm $u$ có thể chứa thiết bị phát tín hiệu lạ khi và chỉ khi khoảng cách lớn nhất từ $u$ đến một trạm bị ảnh hưởng bất kỳ không vượt quá $d$.

Nếu cố định một gốc tùy ý của cây, đường đi từ đỉnh $u$ đến một trạm bị ảnh hưởng bất kỳ chỉ có thể đi xuống cây con của $u$ hoặc đi qua nút cha của $u$ để ra phần còn lại của cây.

Áp dụng kỹ thuật quy hoạch động đổi gốc: lượt duyệt thứ nhất tính khoảng cách xa nhất xuống cây con $down[u]$, lượt duyệt thứ hai truyền thông tin từ nút cha và các nhánh anh em để tính $up[u]$ trong thời gian tổng $O(n)$.