Bedao OI Contest 6 - Đếm cây
View as 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
Comments
bai de vcl
.