

TreeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1304 Accepted Submission(s): 454 Problem Description Alice and Bob are playing with a magic tree This magic tree has $n$ nodes,with $n  1$ magic paths connecting them into a connected block. Node $1$ is at the top of the magic tree (layer $0$). Node $i$ is at the $\text{kth}$ layer, where $k$ is the distance from the node $i$ to the node $1$. Alice and Bob give a mana value on each node. If a magic stone falls on node $i$, it will be sent up to the $k$ layer and appear on the $\text{kth}$ ancestor node of the $i$ layer($k$ is the mana value of node $i$). This node will continue to send up it, and so on. If the layer of node $i$ is less than $k$, this stone will be sent out of the magic tree. Alice is curious, she will modify the magic value of a node, and ask Bob: If you drop a magic stone on the node $x$, how many times does it take to transfer it out of the magic tree? Input Input contains multiple tests The first line contains one integer $T(T \leq 4)$, indicating the number of test cases. The following lines describe all the test cases For each test case: The first line contains an integer $n(n \leq 100000)$, indicating the size of the magic tree. The second line has $n  1$ numbers, and the ith number represents the father of the node $i+1$. The third row has $n$ numbers, and the $\text{ith}$ number represents the initial mana $a_{i}(a_{i} \leq n)$ value of each node. In the fourth line, a number $m(m \leq 100000)$ represents the number of operations. The next $m$ lines, one operation per line. First a number $\text{op}(1 \leq \text{op} \leq 2)$ represents the type of operation. If $\text{op} = = 1$, a number $x$ will be read immediately, indicating that a magic stone is thrown to the node $x$. If $\text{op} = = 2$, it will immediately read in two numbers $x$ and $\text{new_a}$, indicating that the magic value of node $x$ is modified to $\text{new_a}(\text{new_a} \leq n)$. Output For each query with $\text{op} = = 1$, output the answer Sample Input
Sample Output
Hint For the first query: 4\>3\>2\>1\>out For the second query:4\>3\>1\>out Source  
