P13129 [Ynoi Easy Round 2019] 有马加奈
题目背景
题目描述
对于一个节点 $i$ 存在二元组信息 $(a_i,b_i)$。
给定大小为 $n$ 的树。初始化所有节点全为 $(0,0)$。根为 $1$。
给定 $m$ 个操作。
- $1 \ x \ c$ 设当前操作编号为 $z$，对于 $x$ 到根路径，路径上的所有节点 $i$ 的二元组信息，若 $a_i = c$ 那么令 $(a_i,b_i) \leftarrow (c,b_i)$ 否则令 $(a_i,b_i) \leftarrow (c,z)$。
- $2 \ x$ 查询 $(a_x,b_x)$。
输入格式
第一行两个整数 $n,m$ 代表树的大小和操作个数。
接下来一行 $n - 1$ 个数，第 $i$ 个数 $p_i$ 表示点 $i + 1$ 的父亲 $p_i$。
接下来 $m$ 行，每行三个数或两个数代表操作。
输出格式
对于每个询问，输出一行两个数表示答案。
说明/提示
Idea：
FutaRimeWoawaSete，Solution：
FutaRimeWoawaSete，Code：
FutaRimeWoawaSete，Data：
FutaRimeWoawaSete
#### 【数据范围】
| 测试点 | $n$ | $m$ | 特殊性质 |
| :----------: | :------------------: | :-----------------: | :------: |
| $1 \sim 5$ | $\leq \times 10 ^ 5$ | $\leq 10 ^ 5$ | $A$ |
| $6 \sim 10$ | $\leq 10 ^ 5$ | $\leq 10 ^ 5$ | $B$ |
| $11 \sim 15$ | $\le 10 ^ 5$ | $\le \times 10 ^ 5$ | $C$ |
| $16 \sim 20$ | $\le 10^6$ | $\leq 10 ^ 6$ | $/$ |
特殊性质 $A$：满足 $p_i$ 从 $[1,i - 1]$ 里随机选择。
特殊性质 $B$：保证所有 $1$ 操作中 $c = 1$。
特殊性质 $C$：保证 $p_i = i - 1$。
所有数据保证 $n,q \leq 10 ^ 6,x,c \in [1,n]$。
保证样例 $2,3,4,5$ 相应性质对应测试点 $1 \sim 5,6 \sim 10,11 \sim 15,16 \sim 20$ 且使用同一构造方式生成。