Gửi bài giải
Điểm:
1,25 (OI)
Giới hạn thời gian:
4.5s
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 có ~n~ đỉnh. Tìm cách xóa đi một cạnh thuộc cây và thêm vào một cạnh mới, sao cho sau đó, độ dài đường đi dài nhất trên cây là nhỏ nhất có thể. Độ dài của một đường đi được tính bằng số cạnh thuộc đường đi đó.
Input
- Dòng đầu tiên chứa số ~n~ ~(1 \leq n \leq 3 \cdot 10^5)~.
- ~n-1~ dòng sau, mỗi dòng chứa hai số nguyên mô tả một cạnh của cây.
Output
- Dòng đầu tiên in ra độ dài đường đi dài nhất nhỏ nhất tìm được.
- Dòng thứ hai ghi hai số nguyên cho biết cạnh cần xóa.
- Dòng thứ ba ghi hai số nguyên cho biết cạnh cần thêm vào.
Nếu có nhiều lời giải, chỉ cần in ra một lời giải bất kỳ.
Sample Input 1
4
1 2
2 3
3 4
Sample Output 1
2
1 2
1 3
Sample Input 2
7
1 3
2 3
2 7
4 3
7 5
3 6
Sample Output 2
3
2 7
3 5
Bình luận