Tutorial — Vertex Spacing

Đường đi giữa hai đỉnh bất kỳ trên cây luôn là duy nhất và đi qua tổ tiên chung gần nhất của chúng nếu ta cố định một gốc cho cây. Việc tìm khoảng cách giữa các cặp đỉnh có thể quy về việc đếm tại mỗi đỉnh xem có bao nhiêu cặp đỉnh nhận đỉnh đó làm điểm cao nhất trên đường đi kết nối giữa chúng.

Nếu ta biết được số lượng đỉnh ở mỗi độ sâu trong từng nhánh con tính từ một đỉnh, ta có thể ghép các đỉnh từ hai nhánh con khác nhau sao cho tổng khoảng cách tới đỉnh hiện tại đúng bằng $k$. Điều này gợi ý lưu trữ thông tin về số lượng đỉnh ở khoảng cách $j$ với $0 \le j \le k$ trong cây con của mỗi đỉnh.

Sử dụng quy hoạch động trên cây với trạng thái $dp[u][j]$ là số lượng đỉnh trong cây con gốc $u$ có khoảng cách đến $u$ bằng $j$. Khi duyệt qua từng đỉnh con $v$ của $u$, ta kết hợp $dp[u][k - 1 - j]$ với $dp[v][j]$ để cộng dồn vào kết quả trước khi cập nhật $dp[v][j]$ vào $dp[u][j + 1]$.