Path Queries
Xem dạng PDF
Cho một cây có gốc bao gồm ~n~ nút. Các nút được đánh số ~1, 2, ..., n~ và nút ~1~ là gốc của cây. Mỗi nút có một giá trị.
Nhiệm vụ của bạn là xử lý các loại truy vấn sau:
~1~. Thay đổi giá trị của nút ~s~ thành ~x~.
~2~. Tính tổng giá trị trên đường đi từ gốc cây tới nút ~s~.
Input
Dòng đầu vào đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n, q \le 2 \cdot 10^5)~ là số lượng nút và truy vấn. Các nút được đánh số ~1, 2, ..., n~.
Dòng tiếp theo chứa ~n~ số nguyên ~v_1, v_2, ..., v_n~ ~(1 \le v_i \le 10^9)~ lần lượt là giá trị của mỗi nút.
Sau đó, có ~n - 1~ dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên ~a~ và ~b~ ~(1 \le a, b \le n)~ : có một cạnh nối giữa hai nút ~a~ và ~b~.
Cuối cùng, có ~q~ dòng mô tả các truy vấn. Mỗi truy vấn có dạng "1 ~s~ ~x~" hoặc "2 ~s~" ~(1 \le s \le n, 1 \le x \le 10^9~).
Output
- In câu trả lời cho mỗi truy vấn loại ~2~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~30~ | ~n, q \le 1000~ |
| 2 | ~70~ | Không ràng buộc gì thêm. |
Sample Input 1
5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4
Sample Output 1
11
8
Bình luận
Tại sao đề cho n <= 1e5 nhưng mình khai mảng 3e5 phần tử thì lại RTE còn mảng 1e6 phần thử thì lại AC ạ. Đây là 2 đoạn code RTE và AC của mình:
Code RTE
Code AC
bạn cài euler tour như vậy thì kích thước mảng ít nhất phải là ~2n~ chứ không phải ~n~ nhé bạn
oh, em cảm ơn ạ