trang chủ / đề bài / icpc26_mt_e

Tiếp tế giữa mùa tuyết

Đề bài

Mô tả

Một trận bão mùa đông đã phủ tuyết lên các con đường nối một nhóm làng trên núi. Một đội cứu trợ cần thu gom hàng tiếp tế được cất giữ ở các làng. Để di chuyển giữa các làng, đội dùng một xe ủi tuyết để dọn đường.

Có n làng, đánh số từ 1 đến n, được nối với nhau bởi n−1 con đường hai chiều. Giữa hai làng bất kỳ có đúng một đường đi. Làng i đang cất giữ ai thùng hàng, và mỗi con đường có một độ sâu tuyết đã biết.

Một xe ủi tuyết có sức dọn h đi được trên một con đường khi và chỉ khi độ sâu tuyết của con đường đó không vượt quá h. Đội có thể ghé thăm bao nhiêu làng tùy ý và dùng mỗi con đường bao nhiêu lần tùy ý. Đội thu được hàng ở mọi làng mà mình ghé thăm, kể cả làng xuất phát, nhưng mỗi thùng hàng chỉ được thu một lần.

Bạn cần trả lời q truy vấn. Mỗi truy vấn cho một làng xuất phát v và số thùng hàng cần có k. Hãy tìm sức dọn không âm nhỏ nhất để đội thu được ít nhất k thùng hàng, hoặc cho biết điều đó là không thể.

Các truy vấn độc lập với nhau: việc thu hàng ở một truy vấn không ảnh hưởng tới lượng hàng có sẵn ở các truy vấn khác.

Dữ liệu vào

Dòng đầu tiên gồm hai số nguyên n và q (1≤n,q≤200000): số làng và số truy vấn.

Dòng thứ hai gồm n số nguyên a1,a2,…,an (0≤ai≤109), trong đó ai là số thùng hàng được cất ở làng i.

Mỗi dòng trong n−1 dòng tiếp theo gồm ba số nguyên u, v và w (1≤u,v≤n, u≠v, 1≤w≤109), mô tả một con đường hai chiều nối làng u và làng v với độ sâu tuyết w.

Dữ liệu đảm bảo các con đường nối liền tất cả các làng và giữa hai làng bất kỳ có đúng một đường đi.

Mỗi dòng trong q dòng tiếp theo gồm hai số nguyên v và k (1≤v≤n, 1≤k≤1015), mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa sức dọn nhỏ nhất cần thiết để thu được ít nhất k thùng hàng khi xuất phát từ làng v. Nếu không thể, in ra −1.

Ràng buộc

  • 1≤n,q≤200000.
  • 0≤ai≤109.
  • 1≤u,v≤n, u≠v, 1≤w≤109; các con đường tạo thành một cây.
  • 1≤v≤n, 1≤k≤1015 trong mỗi truy vấn.

Ví dụ

Input Output Giải thích
6 7
2 0 4 1 3 5
1 2 3
2 3 7
2 4 3
4 5 6
5 6 7
1 2
1 3
1 6
1 7
3 5
2 1
4 16
0
3
6
7
7
3
-1
Truy vấn 1: làng 1 đã có 2 thùng nên đáp án là 0. Truy vấn 2: với sức dọn 3, xuất phát từ làng 1 đội đến được các làng 1,2,4, tổng cộng 3 thùng. Truy vấn cuối: cần 16 thùng nhưng tổng cộng chỉ có 15 thùng nên đáp án là −1.
4 3
0 2 2 2
1 2 3
1 3 3
1 4 3
1 5
2 2
2 7
3
0
-1
Truy vấn 1: đội phải ghé cả ba làng có hàng, đi qua làng 1 giữa các lần ghé. Sức dọn 3 là đủ.

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