Tree
Contest: ICM Technex 2018 and Codeforces Round 463 (Div. 1 + Div. 2, combined)
Difficulty rating: 2200
Tags: binary search, dp, trees

You are given a node of the tree with index 1 and with weight 0. Let cnt be the number of nodes in the tree at any instant (initially, cnt is set to 1). Support Q queries of following two types:

- $$\mathrm{RW}$$ Add a new node (index cnt + 1) with weight W and add edge between node R and this node.
- $$2 R X = \pi$$ Output the maximum length of sequence of nodes which   starts with R.  Every node in the sequence is an ancestor of its predecessor.  Sum of weight of nodes in sequence does not exceed X.  For some nodes i, j that are consecutive in the sequence if i is an ancestor of j then w[i] ≥ w[j] and there should not exist a node k on simple path from i to j such that w[k] ≥ w[j]

The tree is rooted at node 1 at any instant.

Note that the queries are given in a modified way.

Input format:
First line containing the number of queries Q (1 ≤ Q ≤ 400000).

Let last be the answer for previous query of type 2 (initially last equals 0).

Each of the next Q lines contains a query of following form:

- 1 p q (1 ≤ p, q ≤ 1018): This is query of first type where $$R = p \oplus last$$ and $${ \vec { w } } = q \oplus l a s t$$. It is guaranteed that 1 ≤ R ≤ cnt and 0 ≤ W ≤ 109.
- 2 p q (1 ≤ p, q ≤ 1018): This is query of second type where $$R = p \oplus last$$ and $$X = q \oplus last$$. It is guaranteed that 1 ≤ R ≤ cnt and 0 ≤ X ≤ 1015.

$$a \oplus b$$ denotes bitwise XOR of a and b.

It is guaranteed that at least one query of type 2 exists.

Output format:
Output the answer to each query of second type in separate line.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example,

last = 0

- Query 1: 1 1 1, Node 2 with weight 1 is added to node 1.

- Query 2: 2 2 0, No sequence of nodes starting at 2 has weight less than or equal to 0. last = 0

- Query 3: 2 2 1, Answer is 1 as sequence will be {2}. last = 1

- Query 4: 1 2 1, Node 3 with weight 1 is added to node 2.

- Query 5: 2 3 1, Answer is 1 as sequence will be {3}. Node 2 cannot be added as sum of weights cannot be greater than 1. last = 1

- Query 6: 2 3 3, Answer is 2 as sequence will be {3, 2}. last = 2

Example input:
6
1 1 1
2 2 0
2 2 1
1 3 0
2 2 0
2 2 2

Example output:
0
1
1
2

Example input:
6
1 1 0
2 2 0
2 0 3
1 0 2
2 1 3
2 1 6

Example output:
2
2
3
2

Editorial:
The main idea is that we will use binary lifting. Twice. Let's consider the following O(Q × N) algorithm — for every vertex u (when inserted) find the closest vertex v above it with w[v]  ≥  w[u]. Lets have an array nxt[], such that nxt[u]  =  v. Then the query will be done by simply jumping to the vertex in nxt[], until our sum becomes larger than X. Obviously this is O(Q × Depth) = O(Q × N).
To speed it up, we will have 2 binary liftings. The first one will be for finding the nxt[] and the second one will be for answering the queries. For the first one we will store the 2i-th parent and the maximum weight on the path and for the second one, we will store the 2i-th nxt[] vertex and the sum of the weights on the path. Well that's all and in such a way you can achieve $${\mathcal{O}}(Q\log N)$$.