Phân Hoạch Rừng Không Cô Lập

Buổi 34 — Tree DP & Rerooting Dynamic Programming
Points
75
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 đếm số cách chọn một tập con các cạnh của cây để giữ lại (các cạnh còn lại bị xóa) sao cho trong rừng thu được, mọi thành phần liên thông đều có ít nhất $2$ đỉnh. In ra kết quả theo modulo $10^9 + 7$.

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ố cách chọn cạnh hợp lệ modulo $10^9 + 7$.
Ví dụ
Input Output
4
1 2
2 3
3 4
2
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le u, v \le N$
Draft saved