Thu hoạch

Xem dạng PDF

Gửi bài giải

Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: BAI5.INP
Output: BAI5.OUT

Tác giả:
Nguồn bài:
CHV
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một nông trại có ~n~ khu vườn nối với nhau bởi ~n - 1~ con đường, mỗi con đường nối giữa hai khu vườn với nhau tạo thành dạng một cây đô thị. Khi thu hoạch người ta chọn khu vườn 1 làm gốc của cây đô thị. Khu vườn ~i~ đang có ~a_i~ thùng hoa quả. Ta quy ước nhánh của khu ~u~ bao gồm khu vườn ~u~ và mọi khu vườn nằm trong cây con nhận ~u~ làm gốc.

Trong ngày, diễn ra ~q~ sự kiện thuộc hai loại:

  • ~1~ ~u~ ~x~: Toàn bộ các khu vườn thuộc nhánh khu ~u~, mỗi khu thu hoạch thêm ~x~ thùng hoa quả;
  • ~2~ ~u~: Tính tổng số thùng hoa quả có trong toàn bộ các khu vườn thuộc nhánh của khu ~u~.

Hãy in ra câu trả lời cho các sự kiện loại 2 theo đúng thứ tự dữ liệu đầu vào.

Input BAI5.INP

  • Dòng 1: chứa hai số nguyên ~n~, ~q~ (~1 \le n, q \le 2 \cdot 10^5~) lần lượt là số khu vườn và số sự kiện diễn ra trong ngày;
  • Dòng 2: chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^9~, ~1 \le i \le n~);
  • Tiếp theo là ~n - 1~ dòng, mỗi dòng chứa hai số nguyên ~u~, ~v~ mô tả một con đường (~1 \le u, v \le n~; ~u \ne v~). Các con đường được cho theo thứ tự bất kì và không bảo đảm ~u~ là cha của ~v~. Dữ liệu bảo đảm ~n - 1~ con đường này tạo thành một cây đô thị;
  • Cuối cùng là ~q~ dòng, mỗi dòng mô tả một sự kiện thuộc một trong hai loại theo mô tả đề bài (~1 \le u \le n~; ~1 \le x \le 10^4~).

Output BAI5.OUT

Gồm nhiều dòng, mỗi dòng là một số nguyên tương ứng câu trả lời cho sự kiện loại 2 theo thứ tự dữ liệu đầu vào.

Scoring

Subtask Điểm Ràng buộc
1 20% ~n, q \le 2000~
2 20% Mọi sự kiện loại 1 đều có ~u = 1~
3 20% Con đường thứ ~i~ (~1 \le i \le n - 1~) nối hai khu vườn ~i~ và ~i + 1~
4 40% Không có ràng buộc bổ sung

Sample Input 1

5 5
1 2 3 4 5
1 2
1 3
2 4
2 5
2 2
1 2 10
2 2
2 1
2 4

Sample Output 1

11
41
45
14

Notes

Nhánh của khu vườn 2 gồm ~\{2, 4, 5\}~ với tổng số thùng là ~2 + 4 + 5 = 11~.

Sự kiện tiếp theo cộng 10 thùng cho cả ba khu này nên tổng số thùng của nhánh trở thành ~12 + 14 + 15 = 41~.

Toàn nông trại khi đó có 45 thùng và riêng khu 4 có 14 thùng.


Đang tải...