Cộng trọng số lên cạnh đường đi

General
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$.

Draft saved