Chọn ĐTQG Quảng Trị 2026 - Bài 6 : Nâng cấp hệ thống giao thông

Khu đô thị mới VINNEXT gồm \(N\) biệt thự được đánh số thứ tự từ \(1\) đến \(N\), các biệt thự kết nối với nhau bởi đúng \(N-1\) đoạn đường hai chiều, mỗi đoạn đường nối trực tiếp giữa hai biệt thự. Giữa hai biệt thự bất kỳ luôn tồn tại đường đi thông qua một số đoạn đường.

Công ty xây dựng cầu đường VINTRA trúng thầu nâng cấp hệ thống giao thông của khu đô thị VINNEXT với \(M\) gói thầu khác nhau. Mỗi gói thầu \(M_i\) được xác định bởi bộ ba số \((x_i, y_i, z_i)\) và được hiểu là sẽ nâng cấp các đoạn đường trên đường đi đơn (đường đi đơn là không có đường nào đi lặp lại) từ biệt thự \(x_i\) đến biệt thự \(y_i\) và được sử dụng biệt thự \(z_i\) làm điểm tập kết vật liệu. Việc thực hiện gói thầu \(M_i\) sẽ gây ảnh hưởng tới những biệt thự nằm trên đường đi đơn từ biệt thự \(x_i\) đến biệt thự \(y_i\) (kể cả chính hai biệt thự \(x_i\) và \(y_i\)), mức độ chịu ảnh hưởng của mỗi biệt thự khi thực hiện gói thầu này chính là khoảng cách từ biệt thự đó tới điểm tập kết vật liệu \(z_i\) (khoảng cách là số đoạn đường trên đường đi đơn từ biệt thự đó đến \(z_i\)).

Yêu cầu: Bạn biết trước \(M\) gói thầu, hãy tính tổng mức độ chịu ảnh hưởng của mỗi biệt thự khi thực hiện \(M\) gói thầu này.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) \((1 \le N, M \le 3 \times 10^5)\) lần lượt là số biệt thự và số gói thầu.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) cho biết có đoạn đường hai chiều nối giữa hai biệt thự \(x\) và \(y\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i, y_i, z_i\) \((1 \le x_i, y_i, z_i \le N)\) mô tả gói thầu \(M_i\).

Output

• Ghi ra một dòng gồm \(N\) số nguyên cách nhau một dấu cách, số thứ \(i\) là tổng mức độ chịu ảnh hưởng của biệt thự \(i\).

Example

6 2
1 2
1 3
3 4
3 5
5 6
2 6 4
4 5 1

2 3 2 2 4 3

Scoring

• Subtask 1 (\(25\) điểm): \(N, M \le 10^3\).
• Subtask 2 (\(25\) điểm): Mỗi biệt thự nối trực tiếp với không quá \(2\) biệt thự khác.
• Subtask 3 (\(25\) điểm): Mọi gói thầu \(i\) đều có biệt thự \(z_i\) nằm trên đường đi đơn từ \(x_i\) đến \(y_i\).
• Subtask 4 (\(25\) điểm): Không có ràng buộc gì thêm.