CSES - Tree Diameter | Đường kính của cây
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho một cây gồm \(n\) đỉnh.
Đường kính của cây là khoảng cách xa nhất giữa hai nút bất kì. Hãy xác định đường kính của cây.
Input
- Dòng đầu chứa một số nguyên \(n:\) số lượng nút. Các đỉnh được đánh số \(1,2,3,\dots,n\)
- Sau đó là \(n−1\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) : có một cạnh nối nút \(a\) và \(b\).
Output
- In ra một số nguyên\(:\) đường kính của cây.
Constraints
- \(1 ≤ n ≤ 2⋅10^5\)
- \(1 ≤ a,b ≤ n\)
Example
Sample Input
5
1 2
1 3
3 4
3 5
Sample Output
3
Note
Đường kính \(3\) tương ứng với đường đi \(2 → 1 → 3 → 5\) .
Bình luận
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.