trang chủ / đề bài / icpc19_reg_j

Công lý cho loài kiến

Đề bài

Mô tả

Kiến Chimera là một loài kiến thông minh và chăm chỉ.

Có một đàn kiến Chimera sống ở Đà Nẵng, Việt Nam. Nhờ quy hoạch hạ tầng cẩn thận và làm việc chăm chỉ, chúng đã xây dựng vương quốc gồm n thị trấn, đánh số từ 1 đến n. Các thị trấn được nối với nhau bởi n−1 con đường hai chiều sao cho giữa hai thị trấn bất kỳ có đúng một đường đi đơn.

Mùa đông đang đến! Kiến Chúa dự định phân phát thức ăn cho n thị trấn: thị trấn thứ i sẽ nhận ai đơn vị thức ăn.

Tuy nhiên, đàn kiến cảm thấy kế hoạch này không công bằng. Chúng đòi công lý! Chúng gửi lên q yêu cầu. Mỗi yêu cầu cho bốn thị trấn u, v, x, y sao cho khoảng cách từ u đến v bằng khoảng cách từ x đến y. Ở đây khoảng cách từ thị trấn a đến thị trấn b là số con đường trên đường đi đơn duy nhất từ a đến b.

Gọi p1=u,p2,…,pℓ=v là đường đi đơn từ u đến v, và q1=x,q2,…,qℓ=y là đường đi đơn từ x đến y. Yêu cầu nói rằng với mọi i từ 1 đến ℓ, thị trấn pi và thị trấn qi phải nhận lượng thức ăn bằng nhau.

Việc thay đổi kế hoạch phân phát hóa ra là một bài toán khó. Kiến Chúa có một số nguyên không âm k, và mỗi giây bà có thể thay đổi kế hoạch bằng các bước sau:

  • Chọn một số nguyên t.
  • Chọn một thị trấn i.
  • Tăng hoặc giảm lượng thức ăn của thị trấn i đi t·k+1. Nói cách khác, Kiến Chúa có thể gán ai:=ai+(t·k+1) hoặc ai:=ai−(t·k+1). Sau bước này ai phải là số nguyên không âm, vì không thể phân phát lượng thức ăn âm.

Hỏi Kiến Chúa cần ít nhất bao nhiêu giây để thay đổi kế hoạch sao cho thỏa mãn mọi yêu cầu?

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên n, q và k: số thị trấn, số yêu cầu và số nguyên của Kiến Chúa (1≤n≤5·105, 1≤q≤2·105, 0≤k≤106).

Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤109), trong đó ai là lượng thức ăn ban đầu dự định cho thị trấn i.

n−1 dòng tiếp theo chứa n−1 số nguyên p2,p3,…,pn (1≤pi<i), mỗi số trên một dòng, nghĩa là có một con đường hai chiều nối thị trấn pi với thị trấn i.

Mỗi dòng trong q dòng tiếp theo chứa bốn số nguyên u, v, x, y mô tả một yêu cầu (1≤u,v,x,y≤n). Dữ liệu đảm bảo hai đường đi đơn từ u đến v và từ x đến y có cùng độ dài.

Dữ liệu đảm bảo giữa hai thị trấn bất kỳ có đúng một đường đi đơn, và luôn có thể thỏa mãn cả q yêu cầu.

Dữ liệu ra

In ra một số nguyên là số giây ít nhất mà Kiến Chúa cần để thay đổi kế hoạch phân phát thức ăn.

Ràng buộc

  • 1≤n≤5·105, 1≤q≤2·105, 0≤k≤106.
  • 1≤ai≤109.
  • 1≤pi<i.
  • 1≤u,v,x,y≤n, đường đi từ u đến v và từ x đến y có cùng độ dài.

Ví dụ

Input Output Giải thích
5 3 0
3 1 1 2 1
1
1
3
3
2 3 4 5
1 3 3 4
4 4 5 5
3 Có 4 con đường: (1,2), (1,3), (3,4) và (3,5). Vì k=0 nên mỗi giây Kiến Chúa chỉ có thể tăng hoặc giảm một ai đi 1. Một cách tối ưu là giảm a1 xuống 1 và giảm a4 xuống 1, mất 3 giây.
1 1 5
7
1 1 1 1
0 Ví dụ bổ sung (không có trong đề gốc). Chỉ có một thị trấn, yêu cầu luôn được thỏa mãn nên không cần thay đổi gì.

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