Chi Phí Đường Đi Tuyến Tính
Points
85
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ó hai tham số dương $(a_i, b_i)$.
Với mỗi đỉnh $v$ từ $1$ đến $N$, hãy tìm giá trị nhỏ nhất của biểu thức: \[f(v) = \min_{1 \le u \le N} \left( a_u \cdot \text{dist}(u, v) + b_u \right)\] trong đó $\text{dist}(u, v)$ là tổng trọng số các cạnh trên đường đi đơn nối $u$ và $v$ (với $\text{dist}(v, v) = 0$).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương $N$ ($1 \le N \le 10^5$).
- $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $a_i, b_i$ ($1 \le a_i, b_i \le 10^6$).
- $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$.
Dữ liệu ra
- In ra $N$ số nguyên $f(1), f(2), \dots, f(N)$ trên một dòng, cách nhau bởi dấu cách.
Ví dụ
Dữ liệu vào
3
5 10
2 15
1 30
1 2 3
2 3 4
Dữ liệu ra
10 15 23
Giới hạn
- $1 \le N \le 10^5$, $1 \le a_i, b_i, w \le 10^6$.
Community Discussion