# 描述

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 $k$th 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 $k$th 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≤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≤100000$), indicating the size of the magic tree.
The second line has $n-1$ numbers, and the $i$th number represents the father of the node $i+1$.
The third row has n numbers, and the $i$th number represents the initial mana $a_i$($a_i≤n$) value of each node.
In the fourth line, a number $m$($m≤100000$) represents the number of operations.
The next $m$ lines, one operation per line.
First a number $op$($1≤op≤2$) represents the type of operation.
If $op==1$, a number $x$ will be read immediately, indicating that a magic stone is thrown to the node $x$.
If $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}≤n$).

## Output

For each query with $op==1$, output the answer

## Hint

For the first query: 4->3->2->1->out
For the second query:4->3->1->out

# 思路

• 大佬说这是道LCT的傻逼题，好像的确是这样……
• 每个点向上跳若干步跳到的位置可以使用倍增来查询。
• 如果每个点向能一次跳到的点（加一个点表示树外）连边，则也构成了一棵树。
• 由于要修改一个点能跳的步数，即换父亲，询问链上的距离，所以用LCT维护即可。

0%