#867. SUM3 - Thay đổi trọng số đỉnh

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một cây N đỉnh. Có Q truy vấn tăng giá trị của tất cả các đỉnh nằm trên đường đi từ đỉnh u đến đỉnh v một lượng là x . In ra giá trị của các đỉnh của cây sau khi xử lý hết truy vấn.

Dữ liệu vào:

  • Dòng đầu tiên là số N ;
  • Dòng tiếp theo có N số là giá trị ban đầu của các đỉnh;
  • N-1 dòng tiếp theo thể hiện các cạnh của cây;
  • Dòng tiếp theo số Q ;
  • Q dòng tiếp theo là bộ (u,v,x) tăng tất cả các đỉnh từ u đến v một lượng bằng x .

Dữ liệu ra:

  • Một dòng là giá trị của N đỉnh sau Q truy vấn.

Ví dụ:

Dữ liệu vào:

5
0 0 0 0 0
1 2
2 3
3 4
4 5
2
1 3 5
3 5 7

Dữ liệu ra:

5 5 12 7 7

Giới hạn:

  • 1\le N, Q \le 10^5 .