Sai Heidi đi xa hơn

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Heidi có $n$ người bạn được đánh số từ $0$ đến $n - 1$ . Mạng lưới quan hệ bạn bè tạo thành một cây: có đúng $n - 1$ cặp bạn bè trực tiếp, mỗi cặp $(u, v)$ có một chi phí di chuyển $c$ .

Heidi bắt đầu tại bạn số $0$ và sẽ bị "đẩy" qua lại giữa các bạn theo một chuỗi di chuyển nào đó dọc các cạnh của cây. Trong phiên bản này, không có bạn nào bị thăm quá $k$ lần (lần xuất hiện đầu tiên tại bạn $0$ cũng được tính).

Khi đi giữa hai người bạn $u$ và $v$ , Heidi phải mua vé một lần với chi phí $c (u, v)$ ; sau đó cô có thể đi lại giữa cặp này tự do trong cả ngày. Nói cách khác, mỗi cạnh chỉ bị tính chi phí một lần duy nhất, không phụ thuộc số lần đi qua.

Hãy tính số tiền lớn nhất Heidi có thể phải trả trong trường hợp tệ nhất — tức là tổng chi phí lớn nhất của tập các cạnh được sử dụng, lấy max trên mọi chuỗi di chuyển hợp lệ thoả mãn ràng buộc số lần thăm.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $k$ .
$n - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$ , $v$ , $c$ — mô tả một cạnh giữa $u$ và $v$ với chi phí $c$ .

Dữ liệu ra

In ra một số nguyên — tổng chi phí lớn nhất trong trường hợp xấu nhất.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq k \leq 10^{5}$
$0 \leq u, v \leq n - 1$
$1 \leq c \leq 10^{4}$ (một số test sinh có thể chứa $c = 0$ )
Đồ thị đầu vào luôn là một cây.

Ví dụ

Input	Output	Giải thích
9 3 0 1 1 0 2 1 1 3 2 1 4 2 1 5 2 2 6 3 2 7 3 2 8 3	15	Một chuỗi tệ nhất: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8. Không bạn nào bị thăm quá $3$ lần. Các cạnh đã dùng: $(0, 1), (1, 5), (1, 3), (0, 2), (2, 6), (2, 7), (2, 8)$ với tổng chi phí $1 + 2 + 2 + 1 + 3 + 3 + 3 = 15$ . Cạnh $(1, 4)$ không thể thêm vào vì sẽ cần thăm bạn $1$ tới $4$ lần.
9 5 0 1 1 0 2 1 1 3 2 1 4 2 1 5 2 2 6 3 2 7 3 2 8 3	17	Với $k = 5$ , Heidi có thể duyệt qua tất cả $8$ cạnh của cây, tổng chi phí $1 + 1 + 2 + 2 + 2 + 3 + 3 + 3 = 17$ .
11 6 1 0 7932 2 1 1952 3 2 2227 4 0 9112 5 4 6067 6 0 6786 7 6 3883 8 4 7137 9 1 2796 10 5 6200	54092	Với $k$ đủ lớn, toàn bộ cạnh đều có thể đi qua, đáp án bằng tổng chi phí mọi cạnh.

Bình luận

Không có bình luận tại thời điểm này.