Subtree Queries
Xem dạng PDF
Bạn được cho ~1~ cái cây gồm ~n~ đỉnh, với đỉnh ~1~ là nút gốc, và giá trị tương ứng của từng đỉnh.
Nhiệm vụ của bạn là cần phải thực hiện ~q~ truy vấn có dạng như sau:
~1~. Đổi giá trị của nút ~s~ thành ~x~.
~2~. Tính tổng giá trị của các nút nằm trong cây con gốc ~s~.
Input
Dòng đầu gồm ~2~ số ~n~ và ~q~ (~1 \leq n, q \leq 2 \times 10^5~) tương ứng là số lượng nút trong cây và truy vấn.
Dòng tiếp theo là dãy ~n~ số ~a_1, a_2, a_3, \cdots, a_n~ (~1 \leq a_i \leq 10^9~) là giá trị ban đầu của nút tương ứng trên cây.
Tiếp theo là ~n - 1~ cặp số ~a~, ~b~ (~1 \leq a, b \leq n~) cho ta biết cạnh giữa ~2~ nút ~a - b~ trên cây.
Trong ~q~ dòng cuối cùng là các truy vấn có ~1~ trong ~2~ dạng:
— ~1~ ~s~ ~x~ (~1 \leq s \leq n~, ~1 \leq x \leq 10^9~).
— ~2~ ~s~ (~1 \leq s \leq n~).
Output
Xuất ra từng dòng tương ứng đáp án của từng truy vấn loại ~2~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~50\%~ | ~n \le 5000, q \le 5000~. |
| 2 | ~50\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
5 3
4 2 5 2 1
3 5
1 3
2 1
3 4
2 3
1 5 3
2 3
Sample Output 1
8
10
Sample Input 2
10 10
2 9 19 10 2 3 2 1 9 8
7 2
9 5
3 7
1 8
1 6
8 5
8 10
1 4
3 8
2 3
2 8
1 3 1
2 1
2 10
1 10 2
2 3
1 3 3
2 6
2 2
Sample Output 2
30
50
47
8
12
3
9
Notes
Trong test ví dụ đầu tiên, hình ảnh của cây ban đầu:
Truy vấn "~2~ ~3~" sẽ lấy tổng phần khoanh vùng:
cho ra đáp án là: ~8~.
Sau truy vấn "~1~ ~5~ ~3~", đổi giá trị ở nút ~5~ thành ~3~:
Cuối cùng, truy vấn "~2~ ~3~" sẽ lấy tổng phần khoanh vùng:
cho ra đáp án là: ~10~.
Bình luận
hi
Fan cung ITK65tvquang1