Truy Vấn Đường Đi
Xem dạng PDF
Gửi bài giải
Điểm:
0,20 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
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:~ số lượng nút và truy vấn. Các nút được đánh số ~1,2,... ,n.~
- Dòng tiếp theo có ~n~ số nguyên ~v_1,v_2,... ,v_n:~ 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:~ có một cạnh nối hai nút ~a~ và ~b~.
- Cuối cùng, có ~q~ các dòng mô tả các truy vấn. Mỗi truy vấn có dạng "~1~ ~s~ ~x~" hoặc "~2~ ~s~".
Output
- In câu trả lời cho mỗi truy vấn loại ~2~.
Constraints
- ~1 ≤ n, q ≤ 2⋅10^5~
- ~1 ≤ a, b, s ≤ n~
- ~1 ≤ v_i, x ≤ 10^9~
Example
Sample Input
5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4
Sample Output
11
8
Bình luận
https://oj.vnoi.info/problem/euler_b bài tương tự
ok tks