trang chủ / đề bài / icpc23_mb_f

Bộ máy hành chính

Đề bài

Mô tả

Cho một cây có trọng số trên đỉnh, có gốc cố định, gồm N đỉnh được đánh số từ 0 đến N−1, đỉnh 0 là gốc. Có Q truy vấn thuộc ba loại:

  • 1 u w: đầu tiên, xóa các cạnh nối u với các con của nó. Sau đó tạo một đỉnh mới với chỉ số là chỉ số nhỏ nhất chưa được dùng (tức là đỉnh đầu tiên được tạo bởi truy vấn loại này có chỉ số N, đỉnh thứ hai có chỉ số N+1, ...), có trọng số w, có cha là u và nhận các con cũ của u làm con của nó.
  • 2 u: xóa đỉnh u, các con của u trở thành con của cha u. Đảm bảo u không phải là gốc.
  • 3 u v k: in ra trọng số nhỏ thứ k trên đường đi nối u và v. Đảm bảo k không vượt quá số đỉnh trên đường đi nối u và v (tức là k≤d(u,v)+1, với d(u,v) là khoảng cách giữa u và v).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên N và Q (N,Q≤5·104).

Dòng thứ hai chứa N số nguyên, số thứ i là trọng số của đỉnh i−1. Mọi trọng số đều nằm trong đoạn [0,109].

Mỗi dòng trong N−1 dòng tiếp theo chứa hai số nguyên u và v, cho biết có một cạnh nối u và v.

Cuối cùng là Q dòng, mỗi dòng mô tả một truy vấn theo định dạng ở trên.

Dữ liệu ra

Với mỗi truy vấn loại 3, in đáp án trên một dòng.

Ràng buộc

  • 1≤N,Q≤5·104
  • 0≤ trọng số ≤109
  • Các truy vấn chỉ nhắc tới những đỉnh đang tồn tại; truy vấn loại 2 không xóa gốc.

Ví dụ

Input Output Giải thích
10 10
364715055 598838324 844502191 211147053 438769309 303905477 513518273 332723869 92018216 34702917
1 5
3 2
2 5
6 8
7 5
5 8
8 4
4 0
0 9
3 2 0 1
1 4 951058488
3 9 2 1
1 9 847945860
2 11
1 4 873328923
2 8
1 4 743926561
2 4
1 0 390537674
92018216
34702917
Đường đi 2−5−8−4−0 có trọng số nhỏ nhất 92018216 (đỉnh 8). Sau khi chèn đỉnh 10 giữa 4 và 8, đường đi 9−0−4−10−8−5−2 có trọng số nhỏ nhất 34702917 (đỉnh 9).
5 6
5 3 8 1 6
0 1
0 2
1 3
1 4
3 3 2 2
1 1 4
3 3 4 3
2 1
3 3 2 4
3 5 5 1
3
6
8
4
Đường đi 3−1−0−2 có các trọng số 1,3,5,8. Đỉnh 5 (trọng số 4) được chèn giữa 1 và hai con 3,4; đường đi 3−5−4 có trọng số 1,4,6. Xóa đỉnh 1 thì 5 thành con của 0; đường đi 3−5−0−2 có trọng số 1,4,5,8.

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