Vị quốc vương của đất nước Alpha có 3 chàng hoàng tử. Vì đã đến tuổi "gần đất xa trời", quốc vương muốn giao lại đất nước Alpha cho cả 3 người con quản lý. Đất nước Alpha có
Điều khiến quốc vương đau đầu suốt mấy tháng nay là làm sao để chia đất nước cho 3 người con quản lý một cách công bằng nhất. Cụ thể, nhà vua muốn chia đất nước thành 3 vùng liên thông với nhau, mỗi vùng do một người con quản lý, sao cho chênh lệch giữa vùng nhỏ nhất và lớn nhất là nhỏ nhất có thể.
Kích thước của một vùng được tính bằng số lượng thành phố thuộc vùng đó. Bạn hãy giúp quốc vương tìm ra cách chia tối ưu nhất nhé.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương
tương ứng với số lượng thành phố của vương quốc. −1 dòng tiếp theo, mỗi dòng chứa hai số nguyên dương và tương ứng với có con đường hai chiều nối giữa hai thành phố và .
Kết quả
- In ra độ chênh lệch nhỏ nhất có thể đạt được với cách chia tối ưu.
Ví dụ
Sample Input
9
1 3
2 3
3 4
3 5
5 6
5 7
7 8
7 9
Sample Output
2
Giới hạn
- Subtask1(15%): 3≤
≤200. - Subtask 2 (35%): 3 ≤
≤ 2000. - Subtask 3 (60%): 3 ≤
≤ 200000.
Giải thích

Nguồn: Free Contest
Comments