Path Queries

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Comments

Please read the guidelines before commenting.


  • -1
    tandochuyentin2022  commented on Aug. 31, 2024, 3:52 p.m.

    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


    • 2
      y  commented on Aug. 31, 2024, 5:21 p.m.

      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