trang chủ / đề bài / ld_tst_26_c

Lộ trình

Đề bài

Mô tả

Một quốc gia có n thành phố, được đánh số từ 1 đến n. Các thành phố được kết nối bằng đúng n−1 tuyến đường hai chiều. Hệ thống giao thông được xây dựng sao cho giữa hai thành phố bất kỳ luôn tồn tại duy nhất một đường đi. Nói cách khác, mạng lưới giao thông của quốc gia tạo thành một đồ thị dạng cây, mỗi tuyến đường nối trực tiếp hai thành phố không qua một thành phố trung gian nào cần đúng một ngày để đi qua.

Một đội công tác chuyên trách về kiểm định hạ tầng được giao nhiệm vụ đánh giá chất lượng của một dự án giao thông liên vùng, toàn bộ nhiệm vụ được chia thành m mức theo trình tự thực hiện, đánh số từ 1 đến m. Thành phố thứ i có mức nhiệm vụ là ai. Trong đó, thành phố 1 có mức nhiệm vụ thấp nhất là 1, thành phố n có mức nhiệm vụ cao nhất là m.

Một lộ trình hợp lệ là một lộ trình đi qua một dãy các thành phố u1,u2,…,um thỏa mãn đồng thời các điều kiện sau:

  • u1=1 và um=n.
  • Với mỗi k từ 2 đến m−1, thành phố uk có nhiệm vụ mức k.

Đội công tác thực hiện nhiệm vụ xuất phát từ u1 lần lượt đi tới u2,u3,…,um. Một chặng đường thực hiện nhiệm vụ đi từ thành phố ui đến thành phố uj được tính là hoàn thành khi uj là điểm kết thúc của chặng đường đó với đường đi là ngắn nhất (1≤i<j≤m). Việc đi ngang qua một thành phố trung gian nào đó trong lúc di chuyển giữa hai thành phố ui và uj không được tính là hoàn thành nhiệm vụ, kể cả khi thành phố đó có mức nhiệm vụ cao hơn.

Gọi d(ui,uj) là số ngày ít nhất để đi từ thành phố ui tới thành phố uj, tức độ dài đường đi ngắn nhất giữa chúng trên cây. Thời gian hoàn thành của một lộ trình hợp lệ là tổng số ngày di chuyển của toàn bộ hành trình, cụ thể bằng:

d(u1,u2)+d(u2,u3)+…+d(um−1,um).

Yêu cầu: Hãy tính tổng thời gian hoàn thành của tất cả các lộ trình hợp lệ. Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho 109+7.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên dương n và m (1≤m≤n≤105);
  • Dòng thứ hai chứa n số nguyên dương a1,a2,…,an (1≤ai≤m; a1=1; an=m) tương ứng là mức nhiệm vụ của từng thành phố (dữ liệu đầu vào đảm bảo luôn tồn tại lộ trình hợp lệ);
  • n−1 dòng tiếp theo, mỗi dòng chứa hai số nguyên dương x và y (1≤x,y≤n) mô tả một tuyến đường nối hai thành phố x và y.

Dữ liệu ra

Gồm một số nguyên không âm là tổng thời gian hoàn thành của tất cả các lộ trình hợp lệ, lấy phần dư khi chia cho 109+7.

Ràng buộc

  • 1≤m≤n≤105
  • 1≤ai≤m, a1=1, an=m; luôn tồn tại lộ trình hợp lệ.

Subtasks

  • Subtask 1 (20% số điểm): n≤20.
  • Subtask 2 (20% số điểm): n≤100.
  • Subtask 3 (20% số điểm): n≤5000.
  • Subtask 4 (20% số điểm): Cây có dạng đường thẳng.
  • Subtask 5 (20% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
6 4
1 2 3 3 2 4
3 1
3 2
3 4
3 6
5 6
24 Các thành phố mức 2 là {2,5}, mức 3 là {3,4}. Có bốn lộ trình: 1→2→3→6 (2+1+1=4), 1→2→4→6 (2+2+2=6), 1→5→3→6 (3+2+1=6), 1→5→4→6 (3+3+2=8). Tổng là 24.
5 3
1 2 1 2 3
1 2
2 3
3 4
4 5
8 Ví dụ thêm (không có trong đề gốc). Lộ trình luôn bắt đầu ở thành phố 1 (thành phố 3 cũng có mức 1 nhưng không được chọn làm u1): 1→2→5 dài 1+3=4, 1→4→5 dài 3+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