Tô màu nhỏ nhất
Xem dạng PDF
Gửi bài giải
Điểm:
0,20 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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.
- Nhãn của mỗi đỉnh không vượt quá ~N~.
Input
- Dòng đầu tiên ghi ~N~ ~(1 \leq N \leq 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.
Sample Input
8
1 2
1 3
1 4
1 5
5 6
5 7
5 8
Sample Output
11
2
1
1
1
3
1
1
1
Bình luận
truy vết kiểu gì mn =))
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.