Đường kính của cây
Trong một cây, khoảng cách giữa hai nút là số cạnh trên đường đi duy nhất nối chúng.
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Trong một cây, khoảng cách giữa hai nút là số cạnh trên đường đi duy nhất nối chúng. Khoảng cách lớn nhất có thể có giữa hai nút bất kỳ gọi là đường kính của cây. Đây chính là đại lượng dùng để đo "độ trải rộng" của cây, và cũng là số bước lâu nhất mà một thuật toán lan truyền phải đi.
Yêu cầu
Cho một cây gồm n nút đánh số từ 1 đến n và n - 1 cạnh. Quy ước: nút 1 là gốc của cây; mỗi cạnh có thể được ghi theo chiều bất kỳ (đường kính không phụ thuộc vào việc chọn gốc nào).
Hãy in ra đường kính của cây, tính bằng số cạnh.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Chỉ in đúng một số nguyên, không in thêm chữ nào khác.
Input
- Dòng đầu tiên: số nguyên n (1 <= n <= 10).
- n - 1 dòng tiếp theo: mỗi dòng hai số nguyên u v là một cạnh của cây.
- Khi n = 1 thì không có dòng cạnh nào và đường kính là 0.
Output
Một số nguyên duy nhất: đường kính của cây theo số cạnh.
Ràng buộc
- Dữ liệu luôn là một cây hợp lệ: liên thông, đúng n - 1 cạnh, không có cạnh lặp.
- Thứ tự các dòng cạnh là tùy ý, cạnh có thể ghi con trước cha.
- Đường kính không vượt quá 5.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
4
1 2
1 3
2 4
Output
3
Ví dụ 2
Input
1
Output
0
Giải thích
Dữ liệu vào:
Các khoảng cách đáng chú ý: 4 tới 1 là 2, 4 tới 3 là 3. Không có cặp nút nào xa nhau hơn 3 cạnh, nên đường kính là 3. Kết quả in ra là 3.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
