Phân Công Đường Đi

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Có $N$ đỉnh tạo thành một cây với $N - 1$ cạnh. Cần phân hoạch tập cạnh thành các đường đi (path) trong cây sao cho mỗi cạnh thuộc đúng một đường đi.

Mục tiêu: tối đa hóa $K$ — độ dài tối thiểu của các đường đi trong phân hoạch — tức là tìm $K$ lớn nhất sao cho tồn tại cách phân hoạch với mọi đường đi có độ dài $\geq K$ .

Dữ liệu vào

Dòng 1: số nguyên $N$ ( $2 \leq N \leq 10^{5}$ )
$N - 1$ dòng tiếp theo: mỗi dòng hai số $a$ và $b$ mô tả cạnh nối đỉnh $a$ và $b$

Dữ liệu ra

In ra $K$ — giá trị lớn nhất của độ dài đường đi tối thiểu.

Ràng buộc

$2 \leq N \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
8 1 2 1 3 1 4 4 5 1 6 6 7 7 8	3	Phân hoạch: đường đi 2-1-6-7-8 (dài 4) và 3-1-4-5 (dài 3). $K = 3$ .

Bình luận

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