Hành Trình Trên Cây

Buổi 38 — Divide & Conquer DP
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved