Chi Phí Đường Đi Tuyến Tính

Buổi 46 — Centroid Decomposition Dynamic Programming
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions

Đề 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$.
Draft saved