trang chủ / đề bài / icpcwf24_i

Đạp ga trên thảo nguyên

Đề bài

Mô tả

Chân ga đạp sát sàn. Bánh xe rít lên. Còi hú vang. Các xe cấp cứu làm mọi điều cần thiết để đến nơi nhanh nhất có thể. Thời gian là yếu tố sống còn vì tính mạng con người thường phụ thuộc vào nó.

Cung cấp dịch vụ cấp cứu luôn là một thách thức, đặc biệt ở những vùng thưa dân như thảo nguyên Kazakhstan. Chi phí xây dựng cơ sở hạ tầng rất cao so với số người được phục vụ. Vì vậy cần giảm tối đa cả số con đường lẫn số xe. Mặt khác, giảm thời gian phản ứng của dịch vụ cấp cứu cũng là điều thiết yếu.

Bài toán này xét một mạng lưới đường đã tối thiểu hóa số con đường, nghĩa là giữa hai ngôi làng bất kỳ có đúng một đường đi. Nhờ một khoản tài trợ của chính phủ, Sở Cứu hỏa thảo nguyên Kazakhstan vừa mua được một số xe cứu hỏa mới tinh. Sở muốn đặt trạm cứu hỏa ở một số làng và phân bổ các xe cứu hỏa vào đó sao cho thời gian phản ứng được bảo đảm là tốt nhất.

Nhiệm vụ của bạn là tìm cách đặt các xe cứu hỏa tối ưu, sao cho thời gian cần thiết để một xe cứu hỏa đến được bất kỳ ngôi làng nào là nhỏ nhất. Bạn có thể bỏ qua thời gian tập hợp đội cứu hỏa, thời gian khởi động xe cũng như thời gian đi qua các ngôi làng. Thời gian phản ứng chỉ được tính bằng thời gian di chuyển trên các con đường.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên: số ngôi làng n (1≤n≤100000) và số xe cứu hỏa f (1≤f≤n).

Tiếp theo là n−1 dòng, được đánh số từ 2 đến n. Dòng số i chứa hai số nguyên vi (1≤vi<i) và ti (1≤ti≤10000), cho biết có một con đường hai chiều nối làng i với làng vi, đi hết thời gian ti.

Dữ liệu ra

In ra thời gian phản ứng nhỏ nhất có thể bảo đảm được khi đặt các xe cứu hỏa vào f ngôi làng.

Ràng buộc

  • 1≤n≤100000, 1≤f≤n.
  • 1≤vi<i, 1≤ti≤10000 với mọi 2≤i≤n.

Ví dụ

Input Output Giải thích
6 2
1 8
2 7
2 7
3 6
3 5
8 Đặt hai xe ở làng 2 và làng 3. Làng 1 và làng 4 cách làng 2 lần lượt 8 và 7; làng 5 và làng 6 cách làng 3 lần lượt 6 và 5. Không thể bảo đảm thời gian nhỏ hơn 8.
3 3
1 1000
2 1000
0 Có đủ 3 xe để đặt một xe ở mỗi làng.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0