Bạn có trả lời được các truy vấn VII (Can you answer these queries VII)

Nguồn: SPOJ

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

Đề bài

Mỗi đỉnh có một số nguyên. Hỗ trợ gán cùng một giá trị cho toàn bộ đỉnh trên đường đi $a$ đến $b$ và truy vấn tổng đoạn con liên tiếp lớn nhất trên chính đường đi đó; đoạn rỗng được phép nên đáp án không âm.

Dữ liệu vào

Dòng đầu chứa $n$, dòng hai chứa $n$ giá trị, tiếp theo $n-1$ cạnh, rồi $q$. Mỗi truy vấn là 1 a b hoặc 2 a b c.

Kết quả

Với mỗi truy vấn loại 1, in tổng đoạn con liên tiếp lớn nhất; đoạn rỗng được phép.

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\le10^5$, $|x_i|,|c|\le10000$.

Ví dụ

Input

1
2
5
1 1 1
1 1 1
2 1 1 18
2 1 1 -16
2 1 1 9

Output

2
2

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.