Klasika

시간 제한5초메모리 제한512 MB

요약
가중치 간선을 가진 루트 트리에 노드가 하나씩 추가될 때, 주어진 노드에서 특정 노드의 부분트리 안 임의 노드까지 경로 xor의 최댓값을 매 질의마다 구한다.
난이도

어려움10점 중 9점

유형
트라이, 트리, 비트 연산, 이분 탐색
정답자
아직 제출이 없습니다

문제

In the beginning there was a node denoted as 1 and it represented the root of a tree. Your task is to support Q queries of the form:

  • Add x y – Adds a new node to the tree as a child of node x. The newly added node and node x are connected with an edge of weight y. The newly added node is denoted by a number equal to the number of nodes that the tree consists of after its addition.
  • Query a b – Finds the longest path in a tree which starts in node a and ends in some node from the subtree of node b (which itself is considered to be in its own subtree). The length of the path is defined as exclusive or (xor) of weights of all edges that the path consists of.

입력

The first line contains an integer Q (1 ≤ Q ≤ 200 000) from the task description.

The i-th of the next Q lines contains the i-th query whose format corresponds to one of the queries from the task description. Values x, a and b will refer to an existing node at that moment and value y will not be greater than 230.

출력

You should output an answer to each query of type Query. Each answer should be printed in a separate line in the order in which corresponding queries appear in the input.

예제3

  1. 예제 1

    입력
    4
Add 1 5
Query 1 1
Add 1 7
Query 1 1
    예상 출력
    5
7

  2. 예제 2

    입력
    6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4
    예상 출력
    7
2

  3. 예제 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
    예상 출력
    14
10
13