trang chủ / đề bài / icpc26_mn_g

Khởi động đen

Đề bài

Mô tả

Một cơn bão đã làm sập lưới điện khu vực, mọi trạm biến áp đều mất điện. Lưới điện gồm n trạm biến áp, đánh số từ 1 đến n, và n−1 đường dây truyền tải. Mỗi đường dây nối hai trạm khác nhau và có độ dài là một số nguyên dương. Từ mỗi trạm có thể đi đến mọi trạm khác theo các đường dây, nên các đường dây tạo thành một cây. Khoảng cách giữa hai trạm là tổng độ dài các đường dây trên đường đi duy nhất giữa chúng.

Trạm i được trang bị một bộ khuếch đại có bán kính ri. Ngay khi trạm i có điện, nó cấp điện cho mọi trạm có khoảng cách tới trạm i không quá ri. Các trạm vừa có điện lại cấp điện cho các trạm khác theo cùng quy tắc, và cứ thế tiếp tục cho đến khi không còn trạm nào mới có điện. Nói riêng, một trạm có bán kính 0 không cấp điện cho trạm nào khác.

Để khởi động lại lưới điện, người vận hành bật máy phát khẩn cấp của một số trạm, các trạm này có điện ngay từ đầu. Hãy tìm số trạm ít nhất cần bật máy phát để cuối cùng mọi trạm đều có điện.

Dữ liệu vào

  • Dòng đầu tiên chứa một số nguyên n (1≤n≤3·105): số trạm biến áp.
  • Dòng thứ hai chứa n số nguyên r1,r2,…,rn (0≤ri≤109): bán kính của các bộ khuếch đại.
  • Mỗi dòng trong n−1 dòng tiếp theo chứa ba số nguyên u, v và ℓ (1≤u,v≤n, u≠v, 1≤ℓ≤109), mô tả một đường dây độ dài ℓ nối hai trạm u và v. Dữ liệu bảo đảm các đường dây tạo thành một cây.

Dữ liệu ra

In ra một số nguyên duy nhất: số trạm ít nhất cần bật máy phát.

Ràng buộc

  • 1≤n≤3·105.
  • 0≤ri≤109.
  • 1≤u,v≤n, u≠v, 1≤ℓ≤109; các đường dây tạo thành một cây.

Ví dụ

Input Output Giải thích
7
4 3 0 5 2 0 7
1 2 4
2 3 3
2 4 5
4 5 2
4 6 6
6 7 1
2 Bật máy phát ở trạm 1 và trạm 7. Trạm 7 cấp điện cho trạm 6 (khoảng cách 1) và trạm 4 (khoảng cách đúng bằng 7). Trạm 4 cấp điện cho trạm 2 và trạm 5, trạm 2 cấp điện cho trạm 3. Không trạm nào cấp điện được cho trạm 1 hay trạm 7; chẳng hạn trạm 2 cách trạm 1 một khoảng 4 nhưng bán kính chỉ là 3. Vì vậy cần cả hai máy phát.
4
10 10 0 0
1 2 10
2 3 10
3 4 1
2 Trạm 1 và trạm 2 cấp điện cho nhau, nên một máy phát ở một trong hai trạm này làm trạm 1, 2 và 3 có điện. Trạm 4 cách trạm 3 một khoảng 1, nhưng bán kính của trạm 3 bằng 0, nên trạm 4 cần máy phát riê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