CTREE - Tô màu nhỏ nhất
Giới hạn- Thời gian: 0.098s
- Bộ nhớ: 1536MB
- Mã nguồn: 20000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một cây gồm N nút, hãy tìm cách gán mỗi đỉnh một nhãn nguyên dương sao cho:
- Hai nút có cạnh nối được gán bởi hai nhãn khác nhau.
- Tổng giá trị các nhãn là nhỏ nhất.
Input
Dòng đầu tiên ghi N ( 1 ≤ N ≤ 10000).
N-1 dòng tiếp theo, mỗi dòng ghi hai nút là hai đầu mút của một cạnh thuộc cây.
Output
Dòng đầu tiên ghi S là tổng giá trị nhãn tìm được.
N dòng tiếp theo, dòng thứ i ghi nhãn gán cho đỉnh i trong phép gán tối ưu tìm được.
Example
Input: 8 1 2 1 3 1 4 1 5 5 6 5 7 5 8 Output: 11 3 1 1 1 2 1 1 1
- Người up: hard7771988
- Nguồn bài: Mr Tran Quang Khai