ĐỀ KIỂM TRA ĐỘI TUYỂN HSG LẦN 2 Day 2- Hải Phòng 2020
Cho đồ thị vô hướng liên thông đỉnh, cạnh. Các đỉnh được đánh số từ đến . Độ dài đường đi từ đỉnh đến đỉnh là số lượng đỉnh mà đường đi đi qua.
Ví dụ: Cho cây như hình vẽ:
Trong ví dụ trên, đường đi dài nhất trên cây là đường đi từ đỉnh đến đỉnh (độ dài bằng ) hoặc là đường đi từ đỉnh đến đỉnh cũng có độ dài bằng . Như vậy có tất cả con đường đều có độ dài dài nhất.
Yêu cầu: Hãy xác định độ dài đường đi dài nhất trên cây và số lượng con đường dài nhất này?
Dữ liệu vào:
Dòng đầu ghi số nguyên là số lượng đỉnh của cây.
dòng tiếp theo, mỗi dòng ghi hai số nguyên và tương ứng là có cạnh nối đỉnh và đỉnh .
Dữ liệu ra:
Đưa ra hai số nguyên tương ứng là độ dài đường đi dài nhất trên cây và số lượng đường đi dài nhất trên cây.
Ví dụ:
Dữ liệu vào:
5
1 3
2 3
3 4
4 5
Dữ liệu ra:
4 2
Chú ý: Bài này chấm theo từng ý, trình chấm sẽ đọc hai số nguyên tương ứng với hai ý, mỗi ý đúng được $50% số điểm một test. (Bạn chỉ trả lời một ý cũng phải ghi ra hai số nguyên).
