# Tree

## 题目描述

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: - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/da4b1378453cb99e049b53a08b0ba18e7ba1e551.png) Add a new node (index \$ cnt+1 \$ ) with weight \$ W \$ and add edge between node \$ R \$ and this node. - ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/ed73083bdc6b75130b20ebceb85afda31415dcb3.png) Output the maximum length of sequence of nodes which 1. starts with \$ R \$ . 2. Every node in the sequence is an ancestor of its predecessor. 3. Sum of weight of nodes in sequence does not exceed \$ X \$ . 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] \$ The tree is rooted at node \$ 1 \$ at any instant. Note that the queries are given in a modified way.

## 输入输出格式

### 输出格式

Output the answer to each query of second type in separate line.

## 输入输出样例

### 输入样例 #1

``````6
1 1 1
2 2 0
2 2 1
1 3 0
2 2 0
2 2 2
``````

### 输出样例 #1

``````0
1
1
2
``````

### 输入样例 #2

``````6
1 1 0
2 2 0
2 0 3
1 0 2
2 1 3
2 1 6
``````

### 输出样例 #2

``````2
2
3
2
``````

### 输入样例 #3

``````7
1 1 2
1 2 3
2 3 3
1 0 0
1 5 1
2 5 0
2 4 0
``````

### 输出样例 #3

``````1
1
2
``````

### 输入样例 #4

``````7
1 1 3
1 2 3
2 3 4
1 2 0
1 5 3
2 5 5
2 7 22
``````

### 输出样例 #4

``````1
2
3
``````

## 说明

In the first example, \$ last=0 \$ \- Query 1: 1 1 1, Node \$ 2 \$ with weight \$ 1 \$ is added to node \$ 1 \$ . \- Query 2: 2 2 0, No sequence of nodes starting at \$ 2 \$ has weight less than or equal to \$ 0 \$ . \$ last=0 \$ \- Query 3: 2 2 1, Answer is \$ 1 \$ as sequence will be \$ {2} \$ . \$ last=1 \$ \- Query 4: 1 2 1, Node \$ 3 \$ with weight \$ 1 \$ is added to node \$ 2 \$ . \- 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 \$ \- Query 6: 2 3 3, Answer is \$ 2 \$ as sequence will be \$ {3,2} \$ . \$ last=2 \$