Cập nhật cây con và tổng đường đi từ gốc

Trees
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$, gốc tại đỉnh $1$. Mỗi đỉnh $u$ ban đầu có giá trị $A[u]$. Thực hiện $Q$ truy vấn thuộc hai loại:

  • 1 u v: Cộng thêm $v$ vào giá trị của tất cả các đỉnh trong cây con gốc $u$ (bao gồm cả $u$).
  • 2 w: Tính tổng giá trị hiện tại của tất cả các đỉnh trên đường đi đơn từ gốc $1$ đến đỉnh $w$.
Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N$ và $Q$.
  • Dòng thứ hai chứa $N$ số nguyên $A[1], \dots, A[N]$.
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả một cạnh của cây.
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra tổng giá trị tìm được trên một dòng.

Ví dụ
Input Output
5 4
1 2 3 4 5
1 2
1 3
2 4
2 5
2 4
1 2 10
2 4
2 3
7
27
4
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $-10^6 \le A[i], v \le 10^6$
Draft saved