Tập Độc Lập Cực Đại

Buổi 34 — Tree DP & Rerooting Dynamic Programming
Points
18
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$. 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$
Draft saved