Bedao OI Contest 6 - Đếm cây
Xem dạng PDF
Cho một cây có ~n~ đỉnh có gốc là đỉnh ~1~, đỉnh thứ ~i~ sẽ được phép gán một giá trị bất kỳ trong khoảng ~[L_i, R_i]~. Ta có ~m~ truy vấn dạng ~(A, B, C, D)~, một truy vấn được định nghĩa như sau:
Xem đường đi từ ~A~ đến ~B~ là dãy các đỉnh ~A = u_1, u_2, \dots, u_k = B~. Xem đường đi từ ~C~ đến ~D~ là dãy các đỉnh ~C = v_1, v_2, \dots, v_k = D~. Mỗi truy vấn là một ràng buộc: giá trị được gán ở đỉnh ~u_i~ phải bằng giá trị được gán với đỉnh ~v_i~ với mọi ~i = 1, 2, \dots, k~. Dữ liệu luôn đảm bảo độ dài của hai đường đi ~(A, B)~ và ~(C, D)~ là bằng nhau.
Yêu cầu: Sau mỗi truy vấn thứ ~i~, in ra số cách gán giá trị cho ~n~ đỉnh của cây, sao cho các giá trị này thỏa mãn toàn bộ điều kiện được đề ra từ ~i~ truy vấn đầu tiên của đề bài. Vì kết quả rất lớn nên cần phải được chia dư cho ~10^9 + 7~.
Input
Dòng đầu tiên gồm một số nguyên dương ~n~ (~1 \leq n \leq 2 \times 10^5~) — là số đỉnh của cây.
Dòng thứ hai gồm ~n - 1~ số nguyên ~p_2, p_3, ..., p_n~ (~1 \leq p_i \leq n~) với ~p_i~ là nút cha của đỉnh ~i~.
Trong ~n~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~L_i~ và ~R_i~ (~1 \leq L_i \leq R_i \leq 10^9~) — là khoảng giá trị có thể gán cho đỉnh thứ ~i~.
Dòng tiếp theo gồm một số nguyên dương ~m~ (~1 \leq m \leq 2 \times 10^5~) — là số lượng truy vấn.
Trong ~m~ dòng cuối cùng là những truy vấn có dạng ~(A, B, C, D)~ (~1 \leq A, B, C, D \leq n~).
Output
Sau mỗi truy vấn, in ra đáp án của yêu cầu đề bài khi chia dư cho ~10^9 + 7~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20\%~ | ~n, m \leq 2000~. |
| 2 | ~20\%~ | Đồ thị có dạng đường thẳng. |
| 3 | ~20\%~ | ~n \leq 5 \times 10^4~, đồ thị có nhiều nhất ~10~ nút lá. |
| 4 | ~40\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
5
1 1 3 3
1 7
2 5
4 9
2 8
5 10
3
4 5 3 2
4 3 1 3
1 5 4 1
Sample Output 1
4
4
1
Sample Input 2
8
4 1 3 8 4 3 6
1 10
3 9
2 8
5 7
4 9
1 6
1 6
3 8
5
3 7 8 6
6 2 2 6
1 1 1 1
8 6 6 8
4 1 3 2
Sample Output 2
45360
4320
4320
720
12
Bình luận
Bài này làm sao v mn :<
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.