Liên thông trên cây phiên bản

Đề bài

Mô tả

Cho n đỉnh được đánh số từ 1 đến n. Phiên bản 0 của đồ thị không có cạnh nào.

Có q thao tác được thực hiện lần lượt, mỗi thao tác thuộc một trong hai dạng:

  • 1 p u v — tạo một phiên bản mới bằng cách lấy phiên bản p rồi thêm vào đó cạnh vô hướng (u,v). Nếu đây là thao tác dạng 1 thứ k thì phiên bản mới được đánh số là k. Phiên bản p không bị thay đổi. Cho phép u=v (khuyên) và cho phép thêm một cạnh đã có (cạnh bội).
  • 2 p u v — truy vấn trên phiên bản p: nếu u và v thuộc cùng một thành phần liên thông thì in ra số đỉnh của thành phần đó, ngược lại in ra −1.

Như vậy các phiên bản không xếp thành một dãy: một phiên bản có thể được dùng làm gốc cho nhiều phiên bản mới khác nhau. Dữ liệu đảm bảo p luôn là số hiệu của một phiên bản đã tồn tại ngay trước khi thực hiện thao tác đó.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên n và q.
  • q dòng tiếp theo, mỗi dòng chứa bốn số nguyên mô tả một thao tác theo đúng định dạng ở trên.

Dữ liệu ra

Với mỗi thao tác dạng 2, in ra một dòng chứa đáp số tương ứng, theo thứ tự xuất hiện.

Ràng buộc

  • 1≤n≤105
  • 1≤q≤105
  • 1≤u,v≤n
  • 0≤p≤ số phiên bản đã được tạo trước thao tác đang xét

Ví dụ

Input Output Giải thích
5 7
1 0 1 2
1 1 2 3
2 2 1 3
1 1 4 5
2 3 1 3
2 3 4 5
2 0 1 1
3
-1
2
1
Phiên bản 1 có cạnh (1,2); phiên bản 2 là phiên bản 1 thêm cạnh (2,3) nên 1 và 3 cùng một thành phần gồm 3 đỉnh. Phiên bản 3 lại xuất phát từ phiên bản 1 (không phải phiên bản 2) và thêm cạnh (4,5), nên ở đó đỉnh 1 và 3 không nối nhau, còn 4 và 5 tạo thành phần 2 đỉnh. Truy vấn cuối hỏi trên phiên bản 0: đỉnh 1 luôn cùng thành phần với chính nó, thành phần đó chỉ có 1 đỉnh.
3 6
1 0 1 1
2 1 1 2
1 1 1 2
1 2 1 2
2 3 1 2
2 2 2 3
-1
2
-1
Phiên bản 1 chỉ có khuyên (1,1) nên không nối 1 với 2. Phiên bản 3 thêm cạnh (1,2) lần thứ hai, cạnh bội này không làm thành phần lớn thêm: đáp số vẫn là 2. Trên phiên bản 2, đỉnh 3 vẫn đứng riêng.

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