trang chủ / đề bài / icpcwf18_c

Chinh phục thế giới

Đề bài

Mô tả

Ha ha ha ha!!! Kẻ thù truyền kiếp của bạn, điệp viên đẹp trai lịch lãm Waco Powers, cuối cùng đã sa vào những cái bẫy chết người trong căn cứ núi lửa bí mật của bạn (ít nhất là bạn cho rằng vậy, vì bạn hơi bận nên không tận mắt chứng kiến). Sau bao nhiêu chờ đợi, bạn đã sẵn sàng để CHINH PHỤC THẾ GIỚI!

Không gì có thể cản đường bạn! À, trừ một vấn đề nhỏ về hậu cần. Các đạo quân tàn ác của bạn tuyên bố sẽ không tiếp tục con đường tàn phá không khoan nhượng qua các quốc gia yếu ớt trên thế giới nếu không được trả lương. Không may là bạn đang cạn tiền: một hang ổ núi lửa có nhiều ưu điểm tuyệt vời, nhưng "giá cả phải chăng" không nằm trong số đó. Bạn đã phải rút tiền từ ngân sách đi lại để trả cho đám thuộc hạ vô ơn. Giờ bạn không chắc làm thế nào để thực sự đưa các đạo quân vào vị trí để CHINH PHỤC THẾ GIỚI.

Bạn có bản đồ các quốc gia trên thế giới cùng mọi tuyến vận chuyển hiện có giữa chúng. Mỗi tuyến nối hai quốc gia và có một chi phí cố định cho mỗi đạo quân đi qua nó. Các tuyến được bố trí sao cho giữa hai quốc gia bất kỳ có đúng một cách đi. Bạn biết vị trí hiện tại của từng đạo quân và số đạo quân cần đóng vĩnh viễn tại mỗi quốc gia để khuất phục quốc gia đó. Hãy di chuyển các đạo quân vào vị trí với chi phí nhỏ nhất có thể để bạn có thể CHINH PHỤC THẾ GIỚI.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n: số quốc gia. Tiếp theo là n−1 dòng, mỗi dòng chứa ba số nguyên u, v và c, cho biết có một tuyến hai chiều nối quốc gia u và quốc gia v, chi phí c cho mỗi đạo quân đi qua.

Cuối cùng là n dòng, dòng thứ i chứa hai số nguyên không âm xi và yi: hiện có xi đạo quân ở quốc gia i, và cần ít nhất yi đạo quân ở quốc gia đó trong cấu hình cuối cùng.

Dữ liệu ra

In ra chi phí nhỏ nhất để di chuyển các đạo quân sao cho với mọi i, quốc gia i có ít nhất yi đạo quân.

Ràng buộc

  • 1≤n≤250000.
  • 1≤u,v≤n, 1≤c≤106; các tuyến tạo thành một cây.
  • xi,yi≥0.
  • Tổng số đạo quân ∑xi không nhỏ hơn ∑yi và không vượt quá 106.

Ví dụ

Input Output Giải thích
3
1 2 5
3 1 5
2 1
5 0
1 3
15 Quốc gia 3 thiếu 2 đạo quân: đưa 1 đạo quân thừa từ quốc gia 1 sang (chi phí 5) và 1 đạo quân từ quốc gia 2 qua quốc gia 1 sang (chi phí 10).
6
1 2 2
1 3 5
1 4 1
2 5 5
2 6 1
0 0
1 0
2 1
2 1
0 1
0 1
9 Đạo quân ở quốc gia 2 sang quốc gia 5 (chi phí 5), một đạo quân từ quốc gia 4 đi 4→1→2→6 (chi phí 1+2+1=4).

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