Tóm tắt đề bài

Cho một cây gồm \(N\) đỉnh có trọng số trên các cạnh. Cần chia \(N\) đỉnh này thành đúng \(K\) cụm không rỗng. Đường kính của một cụm là khoảng cách lớn nhất giữa hai đỉnh bất kỳ thuộc cụm đó (khoảng cách tính theo đường đi trên cây ban đầu).

Hãy tìm cách phân hoạch sao cho đường kính lớn nhất trong số \(K\) cụm đạt giá trị nhỏ nhất có thể.

Phân tích

• Điều kiện: \(1 \leq K \leq N \leq 260\ 000\), trọng số cạnh \(1 \leq w \leq 1000\).
• Nhận xét 1: Việc chia \(N\) đỉnh thành \(K\) cụm tối ưu tương đương với việc chọn cắt \(K - 1\) cạnh trên cây để tạo thành \(K\) thành phần liên thông (cây con). Nếu ta có thể chia cây thành \(M \leq K\) cụm mà mỗi cụm đều có đường kính không quá \(D\), ta luôn có thể tùy ý cắt thêm một số cạnh để thu được đúng \(K\) cụm mà không làm tăng đường kính của bất kỳ cụm nào.
• Nhận xét 2: Bài toán có tính chất đơn điệu: nếu tồn tại cách chia cây thành không quá \(K\) cụm sao cho đường kính mỗi cụm \(\leq D\), thì với mọi \(D' > D\) ta cũng luôn chia được. Do đó, ta có thể tìm kiếm nhị phân giá trị đường kính lớn nhất \(D\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Thử tất cả các cách chọn \(K - 1\) cạnh trong số \(N - 1\) cạnh để cắt. Với mỗi cách cắt:

1. Dùng BFS/DFS để tìm các thành phần liên thông.
2. Tính đường kính của từng thành phần liên thông (bằng \(2\) lần BFS/DFS trên mỗi thành phần).
3. Lấy giá trị lớn nhất trong \(K\) đường kính, sau đó tìm giá trị nhỏ nhất qua tất cả các cách cắt.

Hướng giải quyết (Tối ưu)

Nhận xét & Chiến thuật tham lam (Greedy)

Tìm kiếm nhị phân:

• Biên dưới: \(lo = 0\).
• Biên trên: \(hi = \sum w\) (tổng trọng số tất cả các cạnh trên cây).
• Với một giá trị \(D\), ta cần kiểm tra xem có thể cắt cây thành \(\leq K\) cụm sao cho mỗi cụm có đường kính \(\leq D\) hay không.

Hàm kiểm tra check(D):

• Chọn gốc cây tại đỉnh \(1\). Duyệt cây theo thứ tự hậu thứ tự (bottom-up, từ lá lên gốc).
• Với mỗi đỉnh \(v\), ta duy trì độ dài của các nhánh con hướng từ con của \(v\) kéo dài lên \(v\).
• Giả sử \(v\) nhận được danh sách độ sâu của các nhánh từ các con là \(cand = [h_1, h_2, \dots, h_m]\) (sắp xếp giảm dần).
• Nếu có hai nhánh \(h_1, h_2\) mà \(h_1 + h_2 > D\), đường đi nối qua \(v\) giữa hai nhánh này sẽ vượt quá \(D\). Do đó, ta bắt buộc phải cắt bớt một nhánh.
• Để tối ưu cho các đỉnh phía trên, nhánh dài nhất (\(h_1\)) luôn là nhánh bất lợi nhất. Vì vậy, ta tham lam cắt cạnh tương ứng với \(h_1\) (tăng số cụm lên \(1\)) và loại bỏ \(h_1\). Ta lặp lại cho đến khi tổng \(2\) nhánh dài nhất còn lại \(\leq D\) và nhánh dài nhất \(\leq D\).
• Sau khi cắt, nhánh dài nhất còn lại từ con (nếu có) là \(h\). Nhánh này sẽ được nối lên cha của \(v\) với độ dài mới là \(h + w(v, par[v])\).
• Nếu \(h + w(v, par[v]) > D\), ta không thể kéo dài nhánh này lên cha, nên ta cắt cạnh \((v, par[v])\) (tăng số cụm lên \(1\)). Ngược lại, ta truyền độ dài \(h + w(v, par[v])\) lên cha.
• Tại đỉnh gốc (không có cha), thành phần chứa gốc sẽ tạo thành \(1\) cụm cuối cùng.
• Sau khi duyệt xong, nếu tổng số cụm cần tạo \(\leq K\), thì giá trị \(D\) là hợp lệ.

Độ phức tạp

• Thời gian:
  • Mỗi lần kiểm tra check(D): duyệt \(N\) đỉnh. Mỗi nhánh được thêm vào và sắp xếp/xét một lần, mất \(O(N \log (\text{deg})) \approx O(N \log N)\) (hoặc \(O(N)\)).
  • Tìm kiếm nhị phân mất \(O(\log(\sum w))\) bước.
  • Tổng thời gian: \(O(N \log N \log(\sum w))\). Với \(N \leq 260\ 000\), thuật toán chạy trong khoảng 0.2s - 0.5s, đáp ứng tốt giới hạn thời gian.
• Bộ nhớ: \(O(N)\) để lưu đồ thị và các mảng phụ trợ.