Tổng trọng số trên hành trình

Buổi 45 — Heavy-Light Decomposition
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$, mỗi đỉnh $i$ ban đầu có giá trị $A_i$. Bạn cần xử lý $Q$ truy vấn thuộc hai loại:

  • 1 u x: Cập nhật giá trị của đỉnh $u$ thành $x$.
  • 2 u v: Tính tổng giá trị các đỉnh nằm trên đường đi đơn từ $u$ đến $v$.
Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$.
  • Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \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 nối giữa $u$ và $v$.
  • $Q$ dòng cuối cùng, 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 3
1 2 10
2 4 3
2 5 5
10
18
5
Giới hạn

$1 \le N, Q \le 10^5$, $|A_i|, |x| \le 10^9$.

Draft saved