Cộng trọng số lên cạnh đường đi
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây gồm $N$ đỉnh gốc tại $1$, ban đầu tất cả các cạnh đều có trọng số 0. Thực hiện $M$ phép cập nhật $(u, v, w)$: cộng thêm $w$ vào trọng số của tất cả các cạnh trên đường đi đơn giữa $u$ và $v$. Sau đó trả lời $Q$ truy vấn: cho đỉnh $x$, hãy in ra trọng số cuối cùng của cạnh nối giữa $x$ và cha trực tiếp của nó (nếu $x = 1$, in ra 0).
Dữ liệu vào
Dòng đầu chứa ba số nguyên $N, M, Q$. $N - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$. $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$. $Q$ dòng cuối, mỗi dòng chứa một số nguyên $x$.
Dữ liệu ra
Gồm $Q$ dòng, mỗi dòng là trọng số của cạnh $(x, \text{parent}(x))$ hoặc 0 nếu $x = 1$.
Ví dụ
| Input | Output |
|---|---|
| 5 2 4 1 2 1 3 2 4 2 5 4 3 5 5 2 3 1 2 4 5 |
0 5 5 3 |
Giới hạn
$1 \le N, M, Q \le 10^5$, $|w| \le 10^9$.
Community Discussion