Submit solution
Points:
1.50 (partial)
Time limit:
5.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Suggester:
Problem source:
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho trước một cây chỉ gồm một đỉnh ~1~ (và cũng chính là gốc của cây). Nhiệm vụ của bạn là viết chương trình hỗ trợ thực hiện ~Q~ truy vấn ở hai dạng sau:
Add x y
- Thêm một đỉnh vào cây và cho nó làm một đỉnh con của đỉnh ~x~. Đỉnh mới này và đỉnh ~x~ được kết nối bởi một cạnh có trọng số là ~y~. Số hiệu của đỉnh mới bằng số lượng đỉnh của cây trước khi thêm cộng cho ~1~.Query a b
- Tìm đường đi dài nhất bắt đầu từ đỉnh ~a~ và kết thúc tại một đỉnh thuộc cây con gốc ~b~ (bao gồm cả đỉnh ~b~). Độ dài của một đường đi được định nghĩa là tổng xor các trọng số của các cạnh nằm trên đường đi đó.
Input
Dòng đầu tiên chứa số nguyên dương ~Q~ ~(1 \leq Q \leq 200000)~ được nhắc đến ở đề bài.
Dòng thứ ~i~ trong ~Q~ dòng tiếp theo chứa thông tin về truy vấn thứ ~i~ ở định dạng đã được mô tả ở đề bài. Các giá trị ~x~, ~a~ và ~b~ thể hiện những đỉnh đang tồn tại ở trong cây tại thời điểm truy vấn và giá trị ~y~ không vượt quá ~2^{30}~.
Output
Với mỗi truy vấn dạng Query
, in ra một số nguyên trên một dòng riêng biệt thể hiện câu trả lời cho truy vấn tương ứng.
Ví dụ
Sample input 1
4
Add 1 5
Query 1 1
Add 1 7
Query 1 1
Sample output 1
5
7
Sample input 2
6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4
Sample output 2
7
2
Sample input 3
10
Add 1 4
Add 1 9
Add 1 10
Add 2 2
Add 3 3
Add 4 4
Query 4 2
Query 1 3
Add 6 7
Query 1 3
Sample output 3
14
10
13
Ràng buộc
- 12 test đầu có ~Q \leq 200~.
- 12 test sau có ~Q \leq 2000~.
- 12 test sau thỏa ~b=1~với mọi truy vấn
Query
. - 12 test còn lại không có ràng buộc gì thêm.
Comments
bài này time có chặt quá kh ạ
k em