trang chủ / đề bài / lc_tst_26_c

Trạm cứu hộ

Đề bài

Mô tả

Công ty RYZ có n trạm cứu hộ, được đánh số thứ tự từ 1 đến n. Các trạm được nối bởi n−1 tuyến đường hai chiều. Tuyến đường thứ i nối trạm ui với trạm vi và có chiều dài wi. Từ một trạm luôn có thể đi đến mọi trạm khác, giữa hai trạm bất kỳ tồn tại đúng một đường đi.

Trung tâm chỉ huy cần lập phương án cho q tình huống cứu hộ. Trong tình huống thứ j có kj đội cứu hộ xuất phát từ các trạm có chỉ số là s1,s2,…,skj. Cần chọn một trạm trong n trạm cứu hộ có sẵn làm trung tâm điều phối. Trạm được chọn có thể có hoặc không có đội cứu hộ xuất phát. Tất cả các đội cùng di chuyển tới trạm này và chi phí di chuyển của một đội bằng tổng chiều dài các tuyến đường trên đường đi của đội đó. Nếu một đội xuất phát ngay tại trung tâm điều phối thì chi phí của đội bằng 0. Tổng chi phí của tình huống bằng tổng chi phí di chuyển của tất cả các đội cứu hộ đến trung tâm điều phối.

Yêu cầu: với mỗi tình huống, hãy chọn trạm làm trung tâm điều phối sao cho tổng chi phí di chuyển của tất cả các đội là nhỏ nhất và đưa ra giá trị nhỏ nhất đó.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên dương n,q lần lượt là số trạm cứu hộ và số tình huống cứu hộ (1≤n≤5·105; 1≤q≤105).
  • Trong n−1 dòng tiếp theo, dòng thứ i chứa ba số nguyên ui,vi,wi mô tả tuyến đường nối trạm ui và vi với độ dài wi (1≤ui,vi≤n; ui≠vi; 1≤wi≤106).
  • Trong q dòng tiếp theo, dòng thứ j bắt đầu bằng số nguyên kj, sau đó là kj số nguyên s1,s2,…,skj mô tả các trạm xuất phát của những đội tham gia tình huống (1≤kj≤n). Các trạm này đôi một khác nhau và đều thuộc đoạn [1,n].

Dữ liệu bảo đảm tổng tất cả các kj nhỏ hơn hoặc bằng 5·105.

Dữ liệu ra

Gồm q dòng, dòng thứ j chứa tổng chi phí nhỏ nhất của tình huống thứ j.

Ràng buộc

  • 1≤n≤5·105, 1≤q≤105.
  • 1≤wi≤106.
  • 1≤kj≤n, ∑kj≤5·105.

Subtasks

  • Subtask 1 (10% số điểm): n,q≤100.
  • Subtask 2 (10% số điểm): n,q≤500.
  • Subtask 3 (20% số điểm): kj=2, với 1≤j≤q.
  • Subtask 4 (20% số điểm): kj=3, với 1≤j≤q.
  • Subtask 5 (20% số điểm): q=1.
  • Subtask 6 (20% số điểm): Không có giới hạn gì thêm.

Ví dụ

Input Output Giải thích
6 2
1 2 5
1 3 3
2 4 8
2 5 2
3 6 7
3 4 5 6
4 2 3 4 6
25
31
Tình huống 1 (các trạm 4,5,6): chọn trạm 2 làm trung tâm, tổng chi phí nhỏ nhất là 8+2+(7+3+5)=25.
5 3
1 2 4
2 3 1
3 4 6
3 5 2
2 1 4
3 1 4 5
1 5
11
13
0
Ví dụ thêm (không có trong đề gốc). Tình huống 2: chọn trạm 3 (không có đội nào xuất phát ở đó), chi phí 5+6+2=13. Tình huống 3: đội duy nhất đã ở trung tâm.

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