{"problem":{"name":"D. Tree","description":{"content":"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:","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF932D"},"statements":[{"statement_type":"Markdown","content":"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:\n\n*   Add a new node (index _cnt_ + 1) with weight _W_ and add edge between node _R_ and this node.\n*   Output the maximum length of sequence of nodes which\n    1.  starts with _R_.\n    2.  Every node in the sequence is an ancestor of its predecessor.\n    3.  Sum of weight of nodes in sequence does not exceed _X_.\n    4.  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_\\]\n\nThe tree is rooted at node 1 at any instant.\n\n**Note that the queries are given in a modified way.**\n\n## Input\n\nFirst line containing the number of queries _Q_ (1 ≤ _Q_ ≤ 400000).\n\nLet _last_ be the answer for previous query of type 2 (initially _last_ equals 0).\n\nEach of the next _Q_ lines contains a query of following form:\n\n*   1 p q (1 ≤ _p_, _q_ ≤ 1018): This is query of first type where and . It is guaranteed that 1 ≤ _R_ ≤ _cnt_ and 0 ≤ _W_ ≤ 109.\n*   2 p q (1 ≤ _p_, _q_ ≤ 1018): This is query of second type where and . It is guaranteed that 1 ≤ _R_ ≤ _cnt_ and 0 ≤ _X_ ≤ 1015.\n\ndenotes bitwise XOR of _a_ and _b_.\n\nIt is guaranteed that at least one query of type 2 exists.\n\n## Output\n\nOutput the answer to each query of second type in separate line.\n\n[samples]\n\n## Note\n\nIn the first example,\n\n_last_ = 0\n\n\\- Query 1: 1 1 1, Node 2 with weight 1 is added to node 1.\n\n\\- Query 2: 2 2 0, No sequence of nodes starting at 2 has weight less than or equal to 0. _last_ = 0\n\n\\- Query 3: 2 2 1, Answer is 1 as sequence will be {2}. _last_ = 1\n\n\\- Query 4: 1 2 1, Node 3 with weight 1 is added to node 2.\n\n\\- 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\n\n\\- Query 6: 2 3 3, Answer is 2 as sequence will be {3, 2}. _last_ = 2","is_translate":false,"language":"English"}],"meta":{"iden":"CF932D","tags":["binary search","dp","trees"],"sample_group":[["6\n1 1 1\n2 2 0\n2 2 1\n1 3 0\n2 2 0\n2 2 2","0\n1\n1\n2"],["6\n1 1 0\n2 2 0\n2 0 3\n1 0 2\n2 1 3\n2 1 6","2\n2\n3\n2"],["7\n1 1 2\n1 2 3\n2 3 3\n1 0 0\n1 5 1\n2 5 0\n2 4 0","1\n1\n2"],["7\n1 1 3\n1 2 3\n2 3 4\n1 2 0\n1 5 3\n2 5 5\n2 7 22","1\n2\n3"]],"created_at":"2026-03-03 11:00:39"}}