trang chủ / đề bài / icpc26_mt_i

Cùng cấp độ

Đề bài

Mô tả

Một bang hội trong trò chơi nhập vai có N nhân vật, được đánh số từ 1 đến N. Nhân vật thứ i hiện đang ở cấp độ ai.

Có N−1 liên kết trực tiếp giữa các nhân vật, mỗi liên kết nối hai nhân vật, sao cho giữa hai nhân vật bất kỳ có đúng một đường đi (các nhân vật và các liên kết tạo thành một cây).

Hai nhân vật được liên kết trực tiếp với nhau có thể cùng hoàn thành một nhiệm vụ đôi. Mỗi nhiệm vụ đôi tăng cấp độ của cả hai nhân vật tham gia lên đúng 1. Cấp độ của một nhân vật không bao giờ giảm, và nhiệm vụ đôi chỉ được thực hiện giữa hai nhân vật được liên kết trực tiếp.

Trưởng bang hội muốn tất cả các nhân vật trong bang hội đạt cùng một cấp độ.

Yêu cầu: Hãy xác định số nhiệm vụ đôi ít nhất cần thực hiện, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên T, số bộ dữ liệu. Tiếp theo là T bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa số nguyên N.
  • Dòng thứ hai chứa N số nguyên a1,a2,…,aN.
  • N−1 dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v thể hiện một liên kết giữa nhân vật u và nhân vật v.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số nhiệm vụ đôi ít nhất cần thực hiện, hoặc −1 nếu không thể làm cho tất cả các nhân vật trong bang hội đạt cùng một cấp độ.

Ràng buộc

  • 1≤T≤104.
  • 1≤N≤2×105; tổng N của tất cả các bộ dữ liệu không vượt quá 2×105.
  • 0≤ai≤108.
  • 1≤u,v≤N, u≠v; các liên kết tạo thành một cây.

Ví dụ

Input Output Giải thích
4
3
1 0 1
1 2
2 3
2
3 5
1 2
4
0 3 3 2
1 2
1 3
1 4
4
2 0 1 3
1 2
2 3
3 4
2
-1
4
3
Bộ 1: nhân vật 1 và 2 làm một nhiệm vụ, nhân vật 2 và 3 làm một nhiệm vụ; cả ba nhân vật đạt cấp 2. Bộ 2: hai nhân vật luôn lên cấp cùng nhau nên chênh lệch 2 cấp không bao giờ mất đi. Bộ 3: nhân vật 1 làm một nhiệm vụ với nhân vật 2, một nhiệm vụ với nhân vật 3 và hai nhiệm vụ với nhân vật 4; cả bốn nhân vật đạt cấp 4. Bộ 4: cặp 1-2 làm một nhiệm vụ, cặp 2-3 làm hai nhiệm vụ; cả bốn nhân vật đạt cấp 3.
2
6
2 1 0 0 2 1
2 1
3 2
4 1
5 3
6 4
4
0 1 1 1
1 2
1 3
1 4
6
-1
Ví dụ bổ sung. Bộ 1: cây là đường 5−3−2−1−4−6. Không thể cùng đạt cấp 2 (khi đó cặp 2-1 phải làm −1 nhiệm vụ). Ở cấp 3, các cặp 5-3, 3-2, 2-1, 1-4, 4-6 lần lượt làm 1,2,0,1,2 nhiệm vụ, tổng 6. Bộ 2: nếu mọi nhân vật đạt cấp L thì mỗi nhân vật 2,3,4 làm L−1 nhiệm vụ với nhân vật 1, nên 3(L−1)=L, không có nghiệm nguyên.

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