Đường đi trên cây
Xem PDF
Nộp bài
Điểm:
1600
Thời gian:
1.0s
PyPy3
2.0s
Python
2.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Cho n đỉnh và các thao tác nối các đỉnh lại với nhau bằng n - 1 cạnh có trọng số, sao cho sau khi nối tất cả các cạnh sẽ tạo được một đồ thị liên thông. Trong khi các thao tác nối đỉnh được thực hiện, người ta muốn biết xem liệu có tồn tại đường đi giữa hai đỉnh của đồ thị hay không, và trọng số của đường đi (nếu có) là bao nhiêu. Trọng số của một đường đi giữa hai đỉnh trên cây được định nghĩa là tổng XOR của trọng số của tất cả các cạnh trên đường đi giữa hai đỉnh đó.
Input, Output và Subtasks:
Input:
- Dòng đầu tiên gồm hai số nguyên dương n,q lần lượt là số đỉnh và số truy vấn.
- q dòng tiếp theo, mỗi dòng có một trong hai định dạng sau:
+ u v w: tạo một đường đi nối hai đỉnh u và v có trọng số w. Dữ liệu đầu vào đảm có có chính xác n-1 truy vấn cho loại này.? u v: tính trọng số của đường đi giữa hai đỉnh u và v, nếu không có thì in ra -1.
Output:
- Gồm nhiều dòng, mỗi dòng là kết quả của một truy vấn loại 2.
Subtasks:
- n,q\leq 10^6 với mọi testcase.
Sample:
Input:
5 11
? 1 5
+ 1 5 3
+ 5 3 1
? 1 3
+ 5 2 6
? 2 1
? 2 3
? 2 4
+ 1 4 7
? 2 4
? 3 4
Output:
-1
2
5
7
-1
2
5
Notes:
- Truy vấn đầu tiên (hình 1): các đỉnh chưa được nối với nhau nên kết quả là -1.
- Truy vấn thứ hai (hình 2): tồn tại đường đi 1 \rightarrow 5 \rightarrow 3 có trọng số là 2.
- Truy vấn thứ ba (hình 3): tồn tại đường đi 2\rightarrow 5\rightarrow 1 có trọng số là 5.
- Truy vấn thứ tư (hình 3): tồn tại đường đi 2\rightarrow 5\rightarrow 3 có trọng số là 7.
- Truy vấn thứ năm (hình 3): không tồn tại đường đi đến đỉnh 4.
- Truy vấn thứ sáu (hình 4): tồn tại đường đi 2\rightarrow 5\rightarrow 1\rightarrow 4 có trọng số là 2.
- Truy vấn thứ bảy (hình 4): tồn tại đường đi 3\rightarrow 5\rightarrow 1\rightarrow 4 có trọng số là 5.
![]()
Bình luận