Tập Độc Lập Cực Đại
Points
18
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 nhiều đỉnh nhất có thể sao cho không có hai đỉnh nào trong tập con được nối trực tiếp với nhau bởi một cạnh.
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$ mô tả một cạnh.
Dữ liệu ra
- Một số nguyên duy nhất là kích thước lớn nhất của tập độc lập.
Ví dụ
| Input | Output |
|---|---|
| 5 1 2 1 3 3 4 3 5 |
3 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le u, v \le N$
Community Discussion