TRIFT
Xem dạng PDF
Cho một cây gồm ~n~ đỉnh, mỗi đỉnh ~i~ ứng với một dãy ~m~ bit, bit thứ ~j~ nếu như có món quà loại ~j~ xuất hiện tại đỉnh ~i~ và ngược lại nếu bit thứ ~j = 0~. Loại quà thứ ~j~ được gọi là "trọn vẹn" nếu như bit thứ ~j~ của mọi đỉnh trong tập đỉnh của đồ thị con được bật. Do đó, với mọi đồ thị con của đồ thị ban đầu đều ứng với một số nguyên ~k~ là số món quà được "trọn vẹn". Nhiệm vụ của bạn là đếm xem có bao nhiêu đồ thị con của đồ thị ban đầu cho ra ~k~ món quà "trọn vẹn", với ~k~ từ ~0~ đến ~m~.
Input
Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ (~1 \leq n \leq 5000, 1 \leq m \leq 10~).
~n - 1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~u, v~ biểu thị một cạnh của đồ thị.
Tiếp theo là ~n~ dòng, dòng thứ ~i~ gồm ~m~ số nguyên tương ứng với dãy bit của các quà tại đỉnh ~i~.
Output
In ra ~m + 1~ số nguyên trên một dòng, số thứ ~k~ là số lượng đồ thị con liên thông sao cho tồn tại đúng ~k~ món quà trọn vẹn. Kết quả chia lấy dư cho ~10^9 + 7~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~50~ | ~n \le 200~ |
| 2 | ~50~ | Không ràng buộc gì thêm. |
Sample Input 1
3 2
1 2
1 3
1 0
1 1
0 1
Sample Output 1
2 3 1
Notes
Các đồ thị con liên thông là:
1. ~\{1\}~, loại quà: 1.
2. ~\{2\}~, loại quà: ~\{1, 2\}~.
3. ~\{3\}~, loại quà: 2.
4. ~\{1, 2\}~, loại quà: 1.
5. ~\{1, 3\}~, loại quà: ~\varnothing~.
6. ~\{1, 2, 3\}~, loại quà: ~\varnothing~.
Vì vậy, đáp án là ~[2, 3, 1]~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.