Tổng đường đi trên cây với Euler Tour
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một cây gồm $N$ đỉnh có gốc tại đỉnh $1$. Ban đầu, mỗi đỉnh $i$ mang giá trị $a_i$. Có $Q$ truy vấn thuộc một trong hai loại:
1 u x: Thay đổi giá trị của đỉnh $u$ thành $x$.2 u: Tính tổng giá trị của tất cả các đỉnh trên đường đi từ gốc $1$ đến đỉnh $u$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($|a_i| \le 10^9$).
- $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 mô tả một truy vấn (
1 u xvới $|x| \le 10^9$, hoặc2 u).
Dữ liệu ra
- Với mỗi truy vấn loại
2, in ra tổng giá trị trên đường đi từ $1$ đến $u$.
Ví dụ
| Input | Output |
|---|---|
| 5 3 4 2 5 2 1 1 2 1 3 3 4 3 5 2 4 1 3 2 2 4 |
11 8 |
Giới hạn
- $1 \le N, Q \le 10^5, |a_i|, |x| \le 10^9$
Community Discussion