Giới hạn ký tự: 3000
Mùa noel 2019, Nam mua một cây thông noel và cậu quyết định sẽ trang trí cây thông của mình bằng n quả bóng noel có in hình ông già noel trên đó, để cho đẹp, cậu quyết định sẽ treo các quả bóng theo quy tắc như sau:
Bắt đầu từ thân lớn, cậu treo một quả bóng to, sau đó mỗi nhánh nhỏ hơn rẽ ra từ thân lớn, cậu cũng sẽ treo một quả bóng.
Từ nhánh nhỏ, nếu mỗi nhánh nhỏ lại có nhánh nhỏ hơn, cậu lại treo một quả bóng trên mỗi nhánh nhỏ hơn đấy.
Sau đó cậu vẽ lại cách bố trí quả bóng trên cây thông của mình thành một cấu trúc cây, trong đó các đỉnh là các quả bóng ở các nhánh.
Mỗi đỉnh sẽ có đường nối đến các đỉnh khác (gọi là đỉnh con) nếu quả bóng tương ứng với đỉnh đó treo trên cành lớn, còn các đỉnh con là các quả bóng treo ở các cành nhỏ hơn ngay liền kề với đỉnh lớn.
Vì cậu có các hình dán ông già noel với các k màu áo khác nhau, nên cậu muốn dán lên các quả bóng sao cho không có hình nào cùng màu được dán trên các đỉnh là hàng xóm (neighbor) của nhau tức là có đường đi từ đỉnh này sang đỉnh kia.
| NOEL.INP | NOEL.OUT |
4 3 0 1 1 | 18 |
Lâu rồi mới thấy bài về Tree, chưa học gì về Tree nhiều (oof)
Cho cỡ 2,3 ngày đê (mà chắc cũng hết tg rồi, tận 1 tháng rồi mà)