树

题目描述

给定一个权重为 $0$ 的树节点，其索引为 $1$。设 $cnt$ 为树中当前节点的数量（初始时，$cnt$ 的值为 $1$）。支持 $Q$ 个查询，查询类型如下：

• 添加一个新节点（索引为 $cnt+1$，权重为 $W$），并在节点 $R$ 和这个新节点之间添加一条边。
• 输出节点序列的最大长度，该序列满足以下条件：
  1. 以 $R$ 开头。
  2. 序列中的每个节点都是其前驱的祖先。
  3. 序列中节点的权重之和不超过 $X$。
  4. 对于序列中相邻的节点 $i,j$，如果 $i$ 是 $j$ 的祖先，则必须满足 $w[i] \geq w[j]$，并且在从 $i$ 到 $j$ 的简单路径上不能存在权重 $w[k] \geq w[j]$ 的节点 $k$。

树的根节点始终是节点 $1$。

注意，查询以修改后的方式给出。

输入格式

第一行包含查询的数量 $Q$ （$1 \leq Q \leq 400000$）。

设 $last$ 为前一个类型为 $2$ 的查询的答案（初始时，$last$ 等于 $0$）。

接下来的 $Q$ 行包含查询的形式：

• 1 p q （$1 \leq p,q \leq 10^{18}$）：这是第一种类型的查询，其中 和 。保证 $1 \leq R \leq cnt$ 和 $0 \leq W \leq 10^{9}$。
• 2 p q （$1 \leq p,q \leq 10^{18}$）：这是第二种类型的查询，其中 和 。保证 $1 \leq R \leq cnt$ 和 $0 \leq X \leq 10^{15}$。

表示 $a$ 和 $b$ 的按位异或。

保证至少存在一个类型为 $2$ 的查询。

输出格式

对每个类型为 $2$ 的查询，单独输出答案。

样例 #1

样例输入 #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

样例输入 #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

样例输入 #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

样例输入 #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

提示

在第一个示例中，

$last=0$

• 查询 1: 1 1 1，节点 $2$ 的权重为 $1$，并且将其添加到节点 $1$ 下。
• 查询 2: 2 2 0，起始于节点 $2$ 的节点序列的权重和不超过 $0$，所以答案为 $0$。$last=0$。
• 查询 3: 2 2 1，答案为 $1$，序列为 $\{2\}$。$last=1$。
• 查询 4: 1 2 1，节点 $3$ 的权重为 $1$，并且将其添加到节点 $2$ 下。
• 查询 5: 2 3 1，答案为 $1$，序列为 $\{3\}$，节点 $2$ 不能被添加，因为节点的权重和不能超过 $1$。$last=1$。
• 查询 6: 2 3 3，答案为 $2$，序列为 $\{3,2\}$。$last=2$。

# 树

## 题目描述

给定一个权重为 $0$ 的树节点，其索引为 $1$。设 $cnt$ 为树中当前节点的数量（初始时，$cnt$ 的值为 $1$）。支持 $Q$ 个查询，查询类型如下：

- ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/da4b1378453cb99e049b53a08b0ba18e7ba1e551.png) 添加一个新节点（索引为 $cnt+1$，权重为 $W$），并在节点 $R$ 和这个新节点之间添加一条边。
- ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/ed73083bdc6b75130b20ebceb85afda31415dcb3.png) 输出节点序列的最大长度，该序列满足以下条件：
  1. 以 $R$ 开头。
  2. 序列中的每个节点都是其前驱的祖先。
  3. 序列中节点的权重之和不超过 $X$。
  4. 对于序列中相邻的节点 $i,j$，如果 $i$ 是 $j$ 的祖先，则必须满足 $w[i] \geq w[j]$，并且在从 $i$ 到 $j$ 的简单路径上不能存在权重 $w[k] \geq w[j]$ 的节点 $k$。

树的根节点始终是节点 $1$。

注意，查询以修改后的方式给出。

## 输入格式

第一行包含查询的数量 $Q$ （$1 \leq Q \leq 400000$）。

设 $last$ 为前一个类型为 $2$ 的查询的答案（初始时，$last$ 等于 $0$）。

接下来的 $Q$ 行包含查询的形式：

- 1 p q （$1 \leq p,q \leq 10^{18}$）：这是第一种类型的查询，其中 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/330f4f80e58dcf1ca75ad091d4b205adf1d76c24.png) 和 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/5feb6a3312a35a5a19bda784c33f92aaadc2ed58.png)。保证 $1 \leq R \leq cnt$ 和 $0 \leq W \leq 10^{9}$。
- 2 p q （$1 \leq p,q \leq 10^{18}$）：这是第二种类型的查询，其中 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/330f4f80e58dcf1ca75ad091d4b205adf1d76c24.png) 和 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/9c16bf145a73cc846106881a02e5f7cceb5ee2f7.png)。保证 $1 \leq R \leq cnt$ 和 $0 \leq X \leq 10^{15}$。

![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF932D/79cc482b9c190fd9e8196fcbaf085328720025f7.png) 表示 $a$ 和 $b$ 的按位异或。

保证至少存在一个类型为 $2$ 的查询。

## 输出格式

对每个类型为 $2$ 的查询，单独输出答案。

## 样例 #1

### 样例输入 #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

### 样例输入 #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

### 样例输入 #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

### 样例输入 #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

## 提示

在第一个示例中，

 $last=0$

- 查询 1: 1 1 1，节点 $2$ 的权重为 $1$，并且将其添加到节点 $1$ 下。
- 查询 2: 2 2 0，起始于节点 $2$ 的节点序列的权重和不超过 $0$，所以答案为 $0$。$last=0$。
- 查询 3: 2 2 1，答案为 $1$，序列为 $\{2\}$。$last=1$。
- 查询 4: 1 2 1，节点 $3$ 的权重为 $1$，并且将其添加到节点 $2$ 下。
- 查询 5: 2 3 1，答案为 $1$，序列为 $\{3\}$，节点 $2$ 不能被添加，因为节点的权重和不能超过 $1$。$last=1$。
- 查询 6: 2 3 3，答案为 $2$，序列为 $\{3,2\}$。$last=2$。