Tutorial — Optimal Root Server Selection

Nếu chọn một máy chủ bất kỳ làm gốc, dữ liệu chỉ truyền theo một chiều duy nhất từ gốc đến các đỉnh khác dọc theo các cạnh của cây. Thuật toán duyệt đơn giản xuất phát từ từng đỉnh đòi hỏi độ phức tạp $O(n^2)$, không thể đáp ứng giới hạn thời gian khi $n \le 2 \cdot 10^5$.

Khi chuyển máy chủ gốc từ một đỉnh $u$ sang đỉnh kề $v$, hướng truyền dữ liệu cần thiết của hầu hết các cạnh trong mạng lưới đều không đổi. Cạnh duy nhất bị đảo ngược vai trò đối với gốc mới chính là cạnh nối trực tiếp giữa $u$ và $v$.

Áp dụng kỹ thuật quy hoạch động đổi gốc trên cây với thứ tự duyệt BFS để tính trước số phép đảo chiều cho đỉnh $1$, sau đó cập nhật $dp[v] = dp[u] + 1$ hoặc $dp[v] = dp[u] - 1$ trong thời gian $O(1)$ cho mỗi cạnh.