Tổng đường đi trên cây có cập nhật đỉnh

Trees
Points
75
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$. Ban đầu mỗi đỉnh $u$ có giá trị $A[u]$. Thực hiện $Q$ truy vấn thuộc hai loại:

  • 1 u val: Gán $A[u] = val$.
  • 2 u v: Tính tổng giá trị của tất cả các đỉnh nằm trên đường đi đơn từ đỉnh $u$ đến đỉnh $v$.
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ả cạnh của cây.
  • $Q$ dòng tiếp theo, mỗi dòng chứa 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 5
1 2 10
2 4 5
2 3 4
11
19
18
Giới hạn
  • $1 \le N, Q \le 10^5$
  • $-10^6 \le A[i], val \le 10^6$
Draft saved