trang chủ / đề bài / icpc22_reg_k

K đường đi

Đề bài

Mô tả

Trong lý thuyết đồ thị, cây là một đồ thị vô hướng liên thông và không có chu trình. Một cây có n đỉnh có đúng n−1 cạnh. Với mọi cặp đỉnh (u,v) trên cây, có đúng một đường đi đơn giữa u và v. Đường đi đơn là đường đi qua mỗi đỉnh không quá một lần.

Cho một cây gồm n đỉnh, đánh số từ 1 đến n. Đỉnh thứ i có nhãn ai.

Bạn cần chọn k đường đi đơn rời nhau, sao cho đỉnh đầu của mỗi đường đi khác đỉnh cuối của nó, và giá trị lớn nhất của tổng nhãn hai đỉnh đầu mút của một đường đi là nhỏ nhất có thể.

Một cách hình thức, bạn cần chọn k cặp đỉnh (s1,e1),(s2,e2),…,(sk,ek) thỏa mãn tất cả các điều kiện sau:

  • Với mọi i thỏa mãn 1≤i≤k: si≠ei.
  • Xét k đường đi đơn trên cây: đường đi đơn giữa s1 và e1, đường đi đơn giữa s2 và e2, ..., đường đi đơn giữa sk và ek. k đường đi này phải đôi một rời nhau, nói cách khác, mỗi đỉnh của cây thuộc không quá một trong k đường đi.
  • Giá trị max(as1+ae1,as2+ae2,…,ask+aek) nhỏ nhất có thể.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và k (2≤n≤105, 1≤k≤n2).
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (0≤ai≤109).
  • n−1 dòng cuối, mỗi dòng chứa hai số nguyên u và v (1≤u,v≤n) cho biết hai đỉnh u và v được nối trực tiếp bởi một cạnh.

Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây.

Dữ liệu ra

In ra một số nguyên là giá trị nhỏ nhất có thể của biểu thức trên. Nếu không thể chọn k cặp đỉnh thỏa mãn tất cả các điều kiện trên, in ra −1.

Ràng buộc

  • 2≤n≤105, 1≤k≤n2.
  • 0≤ai≤109.

Ví dụ

Input Output Giải thích
4 2
10 20 30 40
1 2
2 3
3 4
70 Chọn hai đường đi 1−2 (tổng 10+20) và 3−4 (tổng 30+40).
4 1
10 20 30 40
1 2
1 3
1 4
30 Chọn đường đi 1−2 với tổng 10+20.
4 2
10 20 30 40
1 2
1 3
1 4
-1 Mọi đường đi có ít nhất hai đỉnh đều đi qua đỉnh 1, nên không thể chọn hai đường đi rời nhau.

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