Vertex Set Path Composite
Xem dạng PDF
Dế Mèn có một bài toán thú vị về cây như sau: cậu có một cây gồm ~n~ đỉnh, đỉnh thứ ~i~ có một hàm tuyến tính ~f_i(x) = a_i x + b_i~ và cạnh thứ ~i~ nối đỉnh ~u_i~ với ~v_i~. Bạn phải xử lý ~q~ truy vấn sau:
~0~ ~p~ ~c~ ~d~: Gán ~f_p~ thành ~cx + d~.
~1~ ~u~ ~v~ ~x~: Coi các đỉnh trên đường đi từ ~u~ đến ~v~ lần lượt là ~p_1 = u~, ~p_2~, ~\cdots~, ~p_k = v~. Tính ~f_{p_k}(...f_{p_2}(f_{p_1}(x)))~ ~\bmod~ ~998244353~
Input
Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ — số đỉnh và số truy vấn.
Trong ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~a_i, b_i~ — chỉ số hàm tuyến tính của đỉnh ~i~.
Trong ~n - 1~ dòng kế tiếp, dòng thứ ~i~ gồm hai số nguyên ~u_i, v_i~ — cạnh ~i~ nối hai đỉnh ~u_i~ và ~v_i~.
Trong ~q~ dòng cuối cùng, truy vấn ~i~ thuộc một trong hai loại trên.
Constraints
~1 \le n, q \le 2 \times 10^5~
~1 \le a_i, c < 998244353~
~0 \le b_i, d, x < 998244353~
~1 \le p, u, v \le n~
~1 \le u_i, v_i \le n~
Output
Với mỗi truy vấn ~1~ in ra kết quả trên một dòng.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~30~ | ~1 \le n, q \le 5000~ |
| 2 | ~70~ | Không có ràng buộc gì thêm |
Sample Input 1
4 3
1 5
4 0
1 1
3 2
1 3
2 4
3 4
1 1 4 3
0 3 2 1
1 4 4 4
Sample Output 1
29
14
Notes
Ở truy vấn thứ nhất, ta có ~f_{4}(f_{3}(f_{1}(x))) = 3(1(1x + 5) + 1) + 2 = 3(1(3 + 5) + 1) + 2 = 29~
Ở truy vấn thứ hai, ta đặt ~f_{3}(x) = 2x + 1~
Ở truy vấn thứ ba, vì đường đi chỉ có một đỉnh nên ta có ~f_{4}(x) = 3x + 2 = 3 \cdot 4 + 2 = 14~
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.