← 返回题目列表

Codeforces · 932/D

D. 树

中文机器翻译题面 查看原题

给定一个索引为 1、权重为 0 的树节点。令 cnt 为任意时刻树中的节点数(最初,cnt 设置为 1)。支持以下两种类型的Q查询:

- $$\mathrm{RW}$$ 添加一个权重为 W 的新节点(索引 cnt + 1),并在节点 R 和该节点之间添加边。
- $$2 R X = \pi$$ 输出以 R 开头的节点序列的最大长度。序列中的每个节点都是其前任节点的祖先。 序列中节点的权重之和不超过X。对于序列中连续的某些节点i, j,如果i是j的祖先,则w[i] ≥ w[j],并且从i到j的简单路径上不应该存在使得w[k] ≥ w[j]的节点k

树在任何时刻都以节点 1 为根。

请注意,查询是以修改后的方式给出的。

输入

第一行包含查询数量 Q (1 ≤ Q ≤ 400000)。

令last 为类型2 的前一个查询的答案(最初last 等于0)。

接下来的 Q 行中的每一行都包含以下形式的查询:

- 1 p q (1 ≤ p, q ≤ 1018):这是第一种类型的查询,其中 $$R = p \oplus last$$ 和 $${ \vec { w } } = q \oplus l a s t$$。保证1 ≤ R ≤ cnt和0 ≤ W ≤ 109。
- 2 p q (1 ≤ p, q ≤ 1018):这是第二种类型的查询,其中 $$R = p \oplus last$$ 和 $$X = q \oplus last$$。保证1 ≤ R ≤ cnt和0 ≤ X ≤ 1015。

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

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

输出

在单独的行中输出第二类型的每个查询的答案。

示例

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

注意

在第一个示例中,

最后= 0

- 查询 1:1 1 1,权重为 1 的节点 2 添加到节点 1。

- 查询 2:2 2 0,从 2 开始的节点序列的权重不小于或等于 0。last = 0

- 查询 3:2 2 1,答案为 1,因为序列将为 {2}。最后= 1

- 查询 4:1 2 1,权重为 1 的节点 3 添加到节点 2。

- 查询 5:2 3 1,答案为 1,因为序列将为 {3}。无法添加节点 2,因为权重之和不能大于 1。last = 1

- 查询 6:2 3 3,答案为 2,因为序列将为 {3, 2}。最后 = 2