Tutorial — Đô Thị

Thay vì đếm số nút chuyển tiếp trên đường đi của từng nút xử lý, hãy đảo ngược góc nhìn để tính xem một nút được chọn làm nút xử lý sẽ đóng góp bao nhiêu vào tổng chất lượng đường truyền chung.

Độ sâu của một nút $u$ tăng chất lượng đường truyền lên $depth[u]$, nhưng mỗi nút xử lý $v$ nằm trong cây con của $u$ sẽ làm giảm lợi ích đó đi $1$. Từ đó, lợi ích ròng độc lập thu được khi chọn nút $u$ làm nút xử lý là $depth[u] - (sz[u] - 1)$ nếu tất cả các nút trong cây con của $u$ cũng được chọn.

Tính giá trị $val[u] = depth[u] - sz[u] + 1$ cho tất cả các nút bằng thuật toán DFS. Sau đó, sắp xếp mảng $val$ giảm dần và lấy tổng của $k$ phần tử lớn nhất.