CSES - Tree Diameter | Đường kính của cây

Xem PDF
Tác giả:
Flower_On_Stone , haidanghutcansa , An09855
Dạng bài
Đ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


  • -3
    N7hoatt    10:38 a.m. 17 Tháng 8, 2023

    Cho một cây gồm \(n\) đỉnh.

    Đường kính của một cây là khoảng cách xa nhất giữa hai đỉnh bất kỳ trong cây. Hãy xác định đường kính của cây được cho.

    Input

    • Dòng đầu tiên gồm một số nguyên \(n\): số đỉnh của cây. Các đỉnh được đánh số từ \(1,2,3,\dots,n\).
    • \(n - 1\) dòng sau 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 hai đỉnh \(a\) và \(b\).

    Output

    • In ra một số nguyên: đường kính của cây đã cho.

    Constraints

    • \(1 \leq n \leq 2 \times 10^5\).
    • \(1 \leq a, b \leq n\).

    Example

    Test

    Input 
    5
1 2
1 3
3 4
3 5
    Output 
    3
    Note

    Đường kính bằng 3 tương ứng với đường đi \(2\)→\(1\)→\(3\)→\(5\).