Problem
Bạn được cho một cây (đồ thị vô hướng tuần hoàn liên thông) gồm n đỉnh.
Tìm kích thước của khớp tối đa của nó (tập hợp các cạnh không liền kề theo cặp).
Đầu vào:
Dòng đầu tiên ghi số n - số đỉnh của cây.
Tiếp theo n-1 dòng, mỗi dòng chứa 2 số a
i và b
i (1 <= a
i, b
i <= n) - cạnh cây.
Đầu ra:
In ra một số - kích thước khớp tối đa của cây đã cho.
Ví dụ:
| Đầu vào |
Đầu ra |
4
1 2
23
3 4 |
2 |
Giải thích:
Kết hợp tối đa của cây này sẽ bao gồm các cạnh 1-2 và 3-4.