#GYM104743F. Yet Another Tree Problem
Yet Another Tree Problem
Description
You are given a tree of $n$ nodes (the nodes are indexed from $1$ to $n$) that is rooted at node $1$.
Each node has a distinct value $a_i$ written on it. Let us define $Sub(u)$ to be the set of all nodes that are in the subtree of node $u$ (node $u$ is also included in its subtree).
You have to process $Q$ queries of $4$ different types. They are as follows:
- 1 p u val: Create a new node with index $u$,parent $p$ and assign $A_u :=$ val.It is guaranteed that $u$ has not appeared before;
- 2 u: Remove all $v$ such that $v \in Sub(u)$ from tree (remove all the nodes in the subtree of $u$);
- 3 u val: Assign the value $A_u := $val;
- 4 u: Print $mex_{v \in Sub(u)} A_v$. (Print the $mex$ of all values of nodes in the subtree of $u$).
It is guaranteed that, at any time, there are no two distinct nodes in the tree that have the same value.
Note: The $mex$ of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$.
The first line contains two space separated integers denoting $n,q (2 \le n,q \le 2 \cdot 10^5)$.
The next line contains $n-1$ space separated integers $p_2, p_3, \dots, p_n(1 \le p_i \le n)$ where $p_i$ denotes an edge between node $p_i$ and $i$ where $p_i$ is the parent of $i$.
The next line contains $n$ space separated integers $a_1, a_2, \dots, a_n(0 \le a_i \le 10^9)$.
The next $q$ lines contain the queries as described above.
It's guaranteed:
- The edges of the initial graph form a valid tree.
- $0 \le$ val $\le 10^9$
- In queries, $1 \le p, u \le n+q$
- At all times there are no two distinct nodes in the tree that have the same value.
- For all $p, u$ that appear in the queries of type $1$, there is a node with index $p$ in the tree,there is no node with the index $u$ and $u$ has not appeared before.
- For all $u$ that appear in the queries of type $2, 3$ and $4$, there is a node with index $u$ in the tree.
For each query of type $4$, print the answer in a new line.
Input
The first line contains two space separated integers denoting $n,q (2 \le n,q \le 2 \cdot 10^5)$.
The next line contains $n-1$ space separated integers $p_2, p_3, \dots, p_n(1 \le p_i \le n)$ where $p_i$ denotes an edge between node $p_i$ and $i$ where $p_i$ is the parent of $i$.
The next line contains $n$ space separated integers $a_1, a_2, \dots, a_n(0 \le a_i \le 10^9)$.
The next $q$ lines contain the queries as described above.
It's guaranteed:
- The edges of the initial graph form a valid tree.
- $0 \le$ val $\le 10^9$
- In queries, $1 \le p, u \le n+q$
- At all times there are no two distinct nodes in the tree that have the same value.
- For all $p, u$ that appear in the queries of type $1$, there is a node with index $p$ in the tree,there is no node with the index $u$ and $u$ has not appeared before.
- For all $u$ that appear in the queries of type $2, 3$ and $4$, there is a node with index $u$ in the tree.
Output
For each query of type $4$, print the answer in a new line.
5 5
1 2 3 3
5 4 3 2 1
1 5 7 0
4 5
2 3
3 2 0
4 2
2
1
Note
- Initially, the tree looks like this:
- After the first query, the tree looks like this:
- After the fourth query, the tree looks like this:
- After the fifth query, the tree looks like this:
