Phủ Đỉnh Cực Tiểu Trên Cây
Points
40
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$. Hãy chọn một tập con gồm ít đỉnh nhất có thể sao cho mọi cạnh của cây đều có ít nhất một đầu mút thuộc tập con đó.
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à số đỉnh ít nhất cần chọn.
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