trang chủ / đề bài / qn_tst_25_e

Lau cây

Đề bài

Mô tả

Cho một đồ thị cây T có n đỉnh (cây là một đồ thị liên thông n đỉnh, n−1 cạnh). Nút lá là đỉnh có đúng một cạnh kề. Ta thực hiện một phép "lau" các cạnh của cây như sau:

  • Chọn hai nút lá bất kì của cây và "lau" tất cả các cạnh trên đường đi ngắn nhất giữa hai nút đó. Nếu số cạnh trên đường đi này là d thì ta nói phép "lau" này mất chi phí d.
  • Quá trình được lặp lại như trên với hai lá khác (trong các nút lá chưa được chọn) cho đến khi tất cả các cạnh của cây đều được "lau" ít nhất một lần.

Như vậy mỗi nút lá được chọn nhiều nhất một lần. Chi phí của một phép "lau" cây là tổng chi phí của tất cả các phép "lau".

Có Q biến thể của cây T. Biến thể thứ i (1≤i≤Q) là một đồ thị cây Ti có được bằng cách thêm vào cây ban đầu Di nút lá. Nút lá v thêm vào nút u của cây ban đầu là thêm một cạnh nối đỉnh u với đỉnh v.

Yêu cầu: Với cây biến thể Ti (1≤i≤Q), hãy tính chi phí nhỏ nhất để "lau" cây Ti; nếu không thể "lau" hết các cạnh của Ti thì in ra −1. Chú ý các cây biến thể là độc lập nhau.

Dữ liệu vào

  • Dòng đầu ghi hai số nguyên N,Q (3≤N≤105; 1≤Q≤105) lần lượt là số đỉnh của cây T và Q biến thể của cây T.
  • N−1 dòng tiếp theo mỗi dòng ghi hai số nguyên u,v (1≤u,v≤N) thể hiện cạnh nối giữa hai đỉnh u,v.
  • Dòng thứ i trong Q dòng tiếp theo, số nguyên đầu tiên Di (1≤Di≤105) là số nút lá được thêm vào, tiếp theo Di số nguyên u thể hiện có một nút lá được thêm vào đỉnh u. Chú ý, có thể có nhiều nút lá mới được thêm vào cùng một đỉnh của đồ thị T và ∑i=1QDi≤105.

Các số trên một dòng được ghi cách nhau một dấu cách.

Dữ liệu ra

Ghi ra Q dòng, mỗi dòng là chi phí nhỏ nhất để "lau" cây biến thể thứ i (hoặc −1 nếu không thể).

Ràng buộc

  • 3≤N≤105; 1≤Q≤105.
  • 1≤u,v≤N; N−1 cạnh ban đầu tạo thành một cây.
  • 1≤Di≤105; ∑i=1QDi≤105.

Subtasks

Điểm được tính theo từng test.

  • Subtask 1 (25% số test): Q=1, cây T có cạnh nối đỉnh 1 với mọi đỉnh u (2≤u≤N), các lá thêm vào không có lá nào nối với đỉnh 1.
  • Subtask 2 (25% số test): N≤20000, Q≤300.
  • Subtask 3 (25% số test): Di=1 (1≤i≤Q).
  • Subtask 4 (25% số test): không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
7 3
1 2
2 4
4 5
5 6
5 7
3 4
1 4
2 2 4
1 1
-1
10
8
Biến thể 1: cây có 5 lá (1,3,6,7 và lá mới), số lá lẻ nên không thể dùng hết các lá, cạnh nối với lá không được chọn không được "lau". Biến thể 2: thêm lá A vào đỉnh 2 và lá B vào đỉnh 4; chọn cặp lá 1−6 mất chi phí 4, cặp A−7 mất chi phí 4, cặp B−3 mất chi phí 2, tổng 10 là nhỏ nhất. Biến thể 3: thêm lá vào đỉnh 1, đỉnh 1 không còn là lá.
7 3
1 2
2 4
4 5
5 6
5 7
3 4
4 1 1 2 6
3 6 6 2
2 2 7
12
11
-1

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