LTC_1D - Đường đi xa nhất

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
wronganswer
Problem types
Allowed languages
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~.

Comments

Please read the guidelines before commenting.


  • 0
    CTV2  commented on May 22, 2024, 5:37 a.m. ← edited

    ai biết làm cho mình xin ý tưởng được không ạ.


    • 2
      dinhvantung0611  commented on Oct. 2, 2024, 2:59 p.m. ← edit 2

      Đâ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)