Truy Vấn Đỉnh Gần Nhất Có Trọng Số Đỉnh
Points
60
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một cây có trọng số gồm $N$ đỉnh đánh số từ $1$ đến $N$. Mỗi đỉnh $i$ có một chi phí ban đầu là $c_i$.
Hãy xử lý $Q$ truy vấn trực tuyến thuộc một trong hai loại sau:
1 v x: Cập nhật chi phí của đỉnh $v$ thành $x$ ($c_v \leftarrow x$).2 v: Tìm giá trị nhỏ nhất của $\text{dist}(u, v) + c_u$ trên tất cả các đỉnh $u \in {1, 2, \dots, N}$, trong đó $\text{dist}(u, v)$ là tổng trọng số các cạnh trên đường đi từ $u$ đến $v$ (với $\text{dist}(v, v) = 0$).
Dữ liệu vào
- Dòng đầu tiên 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 $c_1, c_2, \dots, c_N$ ($0 \le c_i \le 10^{12}$).
- $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^6$) biểu thị một cạnh có trọng số $w$.
- $Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn có dạng
1 v xhoặc2 v($1 \le v \le N$, $0 \le x \le 10^{12}$).
Dữ liệu ra
- Với mỗi truy vấn loại 2, in ra kết quả trên một dòng.
Ví dụ
Dữ liệu vào
4 4
10 5 8 1
1 2 2
2 3 3
2 4 4
2 1
1 3 1
2 1
2 4
Dữ liệu ra
7
6
1
Giới hạn
- $1 \le N, Q \le 10^5$, $1 \le w \le 10^6$, $0 \le c_i, x \le 10^{12}$.
Community Discussion