LTC_1D - Đường đi xa nhất
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, JavaScript, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift, Text
Trang đang trong thời gian nghỉ hè nên cô ấy quyết định dậy sớm từ 6h để tập thể dục giảm cân.
Khu Trang sống có ~N~ thành phố và có ~N-1~ con đường. Sáng sớm Trang sẽ chạy xung quanh khu phố này để tập thể dục.
Hãy tính độ dài đường đi xa nhất giữa ~2~ khu phố mà Trang có thể đi được. Biết rằng từ 1 thành phố có thể đi đến tất cả các thành phố còn lại.
Độ dài đường đi giữa 2 khu phố được tính bằng số con đường đi đi qua trên quãng đường đó.
Input
- Dòng đầu tiên gồm 1 số nguyên dương ~N~ ~(1 \leq N \leq 10^5)~.
~N-1~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~u~, ~v~ mô tả đường đi giữa 2 thành phố ~u~ và ~v~ ~(1 \leq u, v \leq N)~.
Input sẽ có dạng:
N
u1 v1
u2 v2
...
uN vN
Output
- Gồm 1 dòng chứa 1 số nguyên là độ dài đường đi xa nhất giữa ~2~ khu phố mà Trang có thể đi được.
Sample
Input #1
5
1 2
2 3
2 4
1 5
Output #1
3
Giải thích #1
- Đường đi dài nhất sẽ là ~5 \rightarrow 1 \rightarrow 2 \rightarrow 3~ hoặc ~5 \rightarrow 1 \rightarrow 2 \rightarrow 4~. Vậy độ dài đường đi xa nhất sẽ là ~3~.
Bình luận
ai biết làm cho mình xin ý tưởng được không ạ.
Đây là dạng bài cây => chỉ có 1 đường đi giữa 2 gốc bất kì Bạn có thể DFS lần 1 từ gốc 1 để tìm gốc sâu nhất, sau đó DFS lần 2 từ gốc đó đến mọi gốc khác sẽ tìm đc đường đi xa nhất (tương tự bài tìm đường kính của cây ấy bạn)