Hành Trình Trên Cây
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một cây gồm $N$ đỉnh đánh số từ $1$ đến $N$, gốc tại đỉnh $1$. Cạnh nối $(u, v)$ có độ dài $w$. Một người xuất phát từ đỉnh $u$ bất kỳ ($2 \le u \le N$) muốn đi lên gốc $1$. Tại mỗi đỉnh, người đó có thể dừng lại để nghỉ hoặc đi thẳng một mạch lên một tổ tiên thực sự $v$ của nó trên đường về gốc. Nếu đi thẳng từ $u$ lên tổ tiên $v$, chi phí tiêu tốn là $(\text{dist}(u) - \text{dist}(v))^2 + C$, trong đó $\text{dist}(x)$ là khoảng cách từ gốc $1$ đến $x$. Hãy tính tổng chi phí nhỏ nhất để đi từ mỗi đỉnh $u = 2, 3, \dots, N$ về đến gốc $1$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $C$ ($2 \le N \le 10^5, 0 \le C \le 10^{12}$).
- $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^4$) mô tả một cạnh của cây.
Dữ liệu ra
- In ra $N - 1$ số nguyên trên một dòng, số thứ $i$ là chi phí nhỏ nhất từ đỉnh $i + 1$ về gốc $1$.
Ví dụ
| Input | Output |
|---|---|
| 4 10 1 2 3 2 3 4 2 4 5 |
19 45 54 |
| 3 100 1 2 5 2 3 5 |
125 200 |
Giới hạn
- $2 \le N \le 10^5$
- $0 \le C \le 10^{12}$
- $1 \le w \le 10^4$
Community Discussion