Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Subtree MEX

By Hasinur_ · Limits 2s, 1.0 GB

You will be given a balanced binary tree of NN nodes. Each of the nodes of the tree will contain a non-negative integer value. Then, you will be asked to perform QQ queries on the given tree. Each of the queries will be one of the two types described below.

  • 11 KK XX
    This is the 1st1{st} type of query. This query asks you to change the value of KthK^{th} node to XX.

  • 22 II
    This is the 2nd2^{nd} type of query. This query asks you to print the MEX of all integers present in the subtree of IthI^{th} node.

Definition:\textbf{\underline{Definition}}:

  • MEX:{MEX}: In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name "mex" is shorthand for "minimum excluded" value.

  • BalancedBalanced BinaryBinary Tree:Tree:A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 11.

Input

The first line of the input will contain a positive integer NN (1N105)(1 \leq N \leq 10^{5}) which denotes the number of nodes in the tree. The nodes of the tree are numbered from 11 to NN.

The next line will contain NN integers. The ithi^{th} positive integer is the parent node of ithi^{th} node. If the value is 1-1 then the ithi^{th} node is the root node of the tree.

Then, there will be a line containing NN positive integers. The jthj^{th} positive integer is the value assigned to the jthj^{th} node. All the values will be 32-bit non-negative integers.

The fourth line of the input will contain a positive integer QQ (1Q3×105)(1 \leq Q \leq 3 \times 10^{5}) which denotes the number of queries. Each of the next QQ lines will contain one of the two types of queries described in the statement.

  • 11 KK XX
    This is the 1st1{st} type of query. This query asks you to change the value of KthK^{th} node to XX. Here, (1KN)(1 \leq K \leq N) and XX will be a 32-bit non-negative integer.

  • 22 II
    This is the 2nd2^{nd} type of query. This query asks you to print the MEX of all integers present in the subtree of IthI^{th} node. Here, (1I105)(1 \leq I \leq 10^{5}).

Output

Print the MEX value for each 2nd2^{nd} type of query in a new line.

Sample

InputOutput
3
-1 1 1
0 1 2
5
2 1
2 2
2 3
1 1 3
2 1
3
0
0
0

Discussion

Statistics


54% Solution Ratio

arnob918Earliest, 1M ago

EdgedancerFastest, 0.1s

EdgedancerLightest, 29 MB

AlfehsaniShortest, 1783B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.