Thu hoạch
Xem dạng PDFMộ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.