Cặp Ghép Cực Đại Trên Cây

Buổi 34 — Tree DP & Rerooting Dynamic Programming
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved