Đường kính cây

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Đường kính của một cây là khoảng cách lớn nhất giữa hai đỉnh bất kỳ (số cạnh trên đường đi). Cho một cây có $n$ đỉnh, hãy tính đường kính của cây.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ : số đỉnh (đánh số từ $1$ đến $n$ ).

$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ : một cạnh của cây.

Dữ liệu ra

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

Ràng buộc

$1 \leq n \leq 2 \cdot 10^{5}$
$1 \leq a, b \leq n$

Ví dụ

Input	Output	Giải thích
5 1 2 1 3 3 4 3 5	3	Đường đi dài nhất là 2→1→3→4 (hoặc 2→1→3→5), gồm 3 cạnh.
4 1 2 2 3 3 4	3	Cây là một chuỗi, đường kính = 3.

Bình luận

Không có bình luận tại thời điểm này.