Cho một cây gồm đỉnh, đỉnh 1 là gốc. Ban đầu chỉ có đỉnh 1 được điền số với giá trị . Nhiệm vụ: đếm số cách điền các số không âm vào các đỉnh chưa được điền sao cho:
Với mọi đỉnh , số trên đỉnh không nhỏ hơn tổng số trên các đỉnh con trực tiếp của .
Có truy vấn, mỗi truy vấn thuộc một trong hai dạng:
1 u v: điền số vào đỉnh (đỉnh chưa được điền, ).
2 u: xoá số trên đỉnh (đỉnh đang có số, ).
Sau mỗi truy vấn, tính số cách điền hợp lệ (mod ).
Dữ liệu:
Dòng đầu: hai số ().
dòng tiếp theo: mỗi dòng chứa hai số — cạnh của cây.
Dòng tiếp theo: số nguyên ().
dòng cuối: mỗi dòng là một truy vấn dạng 1 u v hoặc 2 u.
Kết quả: Ghi ra dòng: dòng đầu là số cách điền ban đầu, các dòng sau là kết quả sau mỗi truy vấn.
Ví dụ:
Dữ liệu:
3 2
1 2
2 3
1
1 2 1
Kết quả:
6
2
Giới hạn:
Subtask #1: số điểm với .
Subtask #2: số điểm với .
Subtask #3: số điểm chỉ có thao tác loại 1.
Subtask #4: số điểm với chiều cao cây không quá .
Subtask #5: số điểm còn lại không có ràng buộc thêm.
