Gán hàm tại đỉnh, hợp hàm trên đường đi (Vertex Set Path Composite)

Nguồn: Library Checker

Phiên bản: Phước Hưng OJ Extended

Đề bài

Mỗi đỉnh của cây chứa một hàm affine $f(x)=ax+b$ theo modulo $998244353$. Hỗ trợ thay hàm tại một đỉnh và tính hợp hàm theo đúng thứ tự các đỉnh trên đường đi có hướng từ $u$ đến $v$.

Dữ liệu vào

Dòng đầu chứa $n,q$. Tiếp theo $n$ dòng là $(a_i,b_i)$ của $f_i(x)=a_ix+b_i$. Tiếp theo $n-1$ cạnh 0-based. Truy vấn 0 p c d thay hàm ở đỉnh $p$; truy vấn 1 u v x yêu cầu áp dụng lần lượt các hàm trên đường có hướng $u\to v$ vào $x$.

Kết quả

Với mỗi truy vấn loại 1, in giá trị sau khi hợp hàm và áp dụng vào $x$, modulo $998244353$.

Subtask

Subtask 1 (20%)

• Kích thước cây và số thao tác không vượt 20.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• Kích thước cây và số thao tác không vượt 2000.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$; chỉ số đỉnh 0-based; mọi hệ số và $x$ nằm trong $[0,998244353)$.

Ví dụ

Input

1 5
934920615 566121894
1 0 0 809158230
0 0 299738720 566523253
1 0 0 364937308
0 0 693007693 193053012
0 0 704915724 242410315

Output

135724921
823408647

Giải thích

Ví dụ được xử lý đúng theo thứ tự các thao tác. Các truy vấn chỉ quan sát trạng thái hiện tại sau toàn bộ cập nhật đứng trước chúng; kết quả in ra tương ứng với định nghĩa ở phần Đề bài.