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 đỉnh được đánh số từ đến , đỉnh là gốc. Có truy vấn thuộc ba loại:
1 u w: đầu tiên, xóa các cạnh nối 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ố , đỉnh thứ hai có chỉ số , ...), có trọng số , có cha là và nhận các con cũ của làm con của nó.2 u: xóa đỉnh , các con của trở thành con của cha . Đảm bảo không phải là gốc.3 u v k: in ra trọng số nhỏ thứ trên đường đi nối và . Đảm bảo không vượt quá số đỉnh trên đường đi nối và (tức là , với là khoảng cách giữa và ).
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và ().
Dòng thứ hai chứa số nguyên, số thứ là trọng số của đỉnh . Mọi trọng số đều nằm trong đoạn .
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và , cho biết có một cạnh nối và .
Cuối cùng là 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 , in đáp án trên một dòng.
Ràng buộc
- trọng số
- Các truy vấn chỉ nhắc tới những đỉnh đang tồn tại; truy vấn loại 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 có trọng số nhỏ nhất (đỉnh ). Sau khi chèn đỉnh giữa và , đường đi có trọng số nhỏ nhất (đỉnh ). |
| 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 có các trọng số . Đỉnh (trọng số ) được chèn giữa và hai con ; đường đi có trọng số . Xóa đỉnh thì thành con của ; đường đi có trọng số . |
Bình luận