trang chủ / đề bài / hn_tst_25_i

Xóa cạnh

Đề bài

Mô tả

Cho một cây gồm N đỉnh và N−1 cạnh có trọng số. Các cạnh được đánh số từ 1 đến N−1, cạnh thứ i nối cặp đỉnh (u,v) có trọng số c.

Chi phí đường đi giữa hai đỉnh (u,v) là tổng trọng số các cạnh trên đường đi từ u đến v (u≠v). Nếu không tồn tại đường đi từ u đến v thì chi phí đường đi giữa cặp đỉnh (u,v) là 0.

Một cách xóa cạnh được mô tả như sau:

  • Chọn hai số nguyên dương L,R thỏa mãn 1≤L≤R≤N−1;
  • Xóa tất cả các cạnh được đánh số từ L đến R.

Cho trước một số nguyên dương K. Một cách xóa cạnh được gọi là "đẹp" nếu mọi chi phí đường đi giữa cặp đỉnh bất kỳ (sau khi xóa) không vượt quá K. Hai cách xóa cạnh được coi là khác nhau khi có một cạnh trong cách xóa này không có trong cách xóa kia.

Yêu cầu: Đếm số lượng cách xóa cạnh được gọi là "đẹp".

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên N,K (1≤N≤105;1≤K≤109);
  • N−1 dòng sau, dòng thứ i gồm ba số nguyên u,v,c mô tả cạnh thứ i nối đỉnh u và đỉnh v, có trọng số là c (1≤u,v≤N;1≤c≤106). Dữ liệu đảm bảo N−1 cạnh tạo thành một cây.

Dữ liệu ra

Một số nguyên duy nhất là số lượng cách xóa cạnh được gọi là "đẹp" (với N=1 không có cách xóa nào, in ra 0).

Ràng buộc

  • 1≤N≤105; 1≤K≤109.
  • 1≤u,v≤N; 1≤c≤106.

Subtasks

  • Subtask 1 (30% số điểm, 30% số test): N≤20.
  • Subtask 2 (20% số điểm, 20% số test): N≤100.
  • Subtask 3 (20% số điểm, 20% số test): N≤2500.
  • Subtask 4 (20% số điểm, 20% số test): cây là một đường thẳng.
  • Subtask 5 (10% số điểm, 10% số test): không có ràng buộc thêm.

Bài được chấm theo từng test, mỗi test có cùng số điểm.

Ví dụ

Input Output Giải thích
6 12
1 2 3
1 4 5
2 3 6
2 5 4
3 6 9
9 Các cách xóa đẹp: (L,R)=(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5). Ví dụ L=R=3: xóa cạnh 3, đường đi đắt nhất là từ đỉnh 4 đến đỉnh 5 với chi phí 5+3+4=12≤K. Còn L=R=1 không đẹp vì đường đi từ đỉnh 2 đến đỉnh 6 có chi phí 6+9=15>12; L=4,R=5 không đẹp vì đường đi từ đỉnh 3 đến đỉnh 4 có chi phí 6+3+5=14>12.
5 6
1 2 4
3 4 5
2 3 3
4 5 2
6 Cây là đường thẳng 1−2−3−4−5. Xóa một cạnh duy nhất thì luôn còn một đường đi có chi phí lớn hơn 6 (ví dụ xóa cạnh 3 còn đường 3−4−5 chi phí 7). Mọi cách xóa từ hai cạnh trở lên đều đẹp: (1,2),(1,3),(1,4),(2,3),(2,4),(3,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