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:
Mr Tran Quang Khai
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

Hãy đọc nội quy trước khi bình luận.



  • -1
    trongtenlinhcbhk64  đã bình luận lúc 6, Tháng 3, 2023, 8:55

    truy vết kiểu gì mn =))


  • -9
    leduykhongngu  đã bình luận lúc 23, Tháng 5, 2021, 12:19

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -18
      lamcherry0208  đã bình luận lúc 26, Tháng 6, 2021, 18:31

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.