Cặp Ghép Cực Đại Trên Cây
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$. Một cặp ghép (matching) là một tập các cạnh đôi một không có chung đầu mút. Hãy tìm số cạnh lớn nhất trong một cặp ghép trên cây.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$.
Dữ liệu ra
- Một số nguyên duy nhất là kích thước cặp ghép cực đại.
Ví dụ
| Input | Output |
|---|---|
| 5 1 2 1 3 3 4 3 5 |
2 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le u, v \le N$
Community Discussion