COCI 2019/2020 - Contest 4 - Klasika
Xem dạng PDF
Gửi bài giải
Điểm:
1,50 (OI)
Giới hạn thời gian:
5.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Người đăng:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
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.
Bình luận
bài này time có chặt quá kh ạ
k em