COCI 2019/2020 - Contest 4 - Klasika

View as PDF
Submit solution
Points: 1.50 (partial)
Time limit: 5.0s
Memory limit: 512M
Input: stdin
Output: stdout
Suggester:
Mondeus
Problem source:
COCI 2019/2020 - Contest 4
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

Please read the guidelines before commenting.