「MCOI-04」重型管制巡航机

这是一个作战部署命令。 我们已经从国家安全局获得了有关敌方重型指挥巡洋舰的部分机密情报。 敌方巡航机的正式名称已被确认为 P-1112 Aigaion。 空中舰队中包含一种 Kottos 中型巡航机负责电子支援，还有一种 Gyges 中型巡航机负责近程防空。 Aigaion，作为指挥机，负责一切与巡航导弹相关的事务。 在获得这些情报之后，我们可以草拟一个摧毁 Aigaion 的计划。 仔细听好了。 Aigaion 只能在机体前部接受空中加油。 多架加油机必须同时处在 Aigaion 前方才能进行加油作业。 当加油机在 Aigaion 前部进行加油时，Aigaion 的雷达探测能力会暂时削弱。 这里就是关键点了。 Aigaion 在进行加油时，其雷达基本完全无法探测在其前方飞行的物体。 如果你们能维持在一个固定航线并在一个特定高度上飞行，你们就能在不被敌军发现的情况下，从空中接近 Aigaion。 所以我们解决掉这只怪物的最佳时机就是它进行空中加油的时候。 Aigaion 的预定航线图也包含在这份情报中。 简报结束后，我们将在机库再次检查航线图。 快去准备吧。 ………… Garuda 队，交战！ $$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 09} \\\Large\text{Heavy Command Cruiser}\\\tiny -\ The\ Dead\ Sea\ -$$

在平面上给定一棵有根树，树根为 $1$，根的深度为 $0$。 对于深度为 $x$ 的节点，其 **纵坐标** 为 $n-x+1$。 对于一个节点的所有子节点，**从左到右按照编号升序排列**。每条边都是一条 **连接两个点的线段**。 每一个叶子节点都有一条 **平行于 $y$ 轴且向 $y$ 轴负方向无限延伸的射线**，根节点有一条 **平行于 $y$ 轴且向 $y$ 轴正方向无限延伸的射线**。 **任意两条线段或射线只在树的节点处相交。** 如果你不理解这个树是怎么画的，可以阅读样例 1 解释。 给定 $q$ 组 $u,v$，你现在要从点 $u$ 开始在平面上自由移动，但是你不能经过除 $u,v$ 以外的任何一个点，且每经过一条线段或射线就会产生 $1$ 的代价。 你的目标是移动到点 $v$，你需要求出移动过程产生的最小代价。

由于直接输入会造成巨大的输入量，所以本题采用特殊的输入方式。 给定如下随机数生成器： ```cpp namespace GenHelper { unsigned z1,z2,z3,z4,b; unsigned rand_() { b=((z1<<6)^z1)>>13; z1=((z1&4294967294U)<<18)^b; b=((z2<<2)^z2)>>27; z2=((z2&4294967288U)<<2)^b; b=((z3<<13)^z3)>>21; z3=((z3&4294967280U)<<7)^b; b=((z4<<3)^z4)>>12; z4=((z4&4294967168U)<<13)^b; return (z1^z2^z3^z4); } } void srand(unsigned x) {using namespace GenHelper; z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;} int read() { using namespace GenHelper; int a=rand_()&32767; int b=rand_()&32767; return a*32768+b; } ``` 第一行三个整数 $n,q,s$。 接下来一行 $n-1$ 个整数描述树的结构。第 $i$ 个数代表 $i+1$ 号节点的父亲的编号 $f_i$。 接下来，如果 $s=-1$，则标准输入中的接下来 $q$ 行每行会有两个空格分隔的整数，代表询问的 $u'$ 和 $v'$；设上一次询问的答案为 $\text{lastans}$，你真正要处理的询问是 $u=u'\oplus \text{lastans}$ 和 $v=v'\oplus \text{lastans}$，其中 $\oplus$ 表示异或运算。如果这是第一次询问，则 $\text{lastans}=0$。 否则，你需要先调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $u$，再调用一次 $(\text{read}()\oplus \text{lastans})\bmod n+1$ 得到询问的 $v$。

如果 $s=-1$，则输出 $q$ 行，每行是对应询问的答案。 如果 $s\geq 0$，则输出两个空格分隔的整数，分别表示所有答案的异或和和所有答案的和。

9 4 -1
1 1 2 2 2 3 7 7
4 7
7 2
5 2
4 8

1
0
0
1

30 1 -1
1 2 3 4 5 6 7 7 9 9 11 11 12 13 13 14 17 18 19 20 21 19 23 22 22 25 25 28 29 
6 30

2

30 10000 20051130
1 2 3 4 5 6 7 7 9 9 11 11 12 13 13 14 17 18 19 20 21 19 23 22 22 25 25 28 29

2 6362

**For the enhanced version, see [P7434](https://www.luogu.com.cn/problem/P7434).** #### 样例 1 解释 第二次实际是询问 $u=6,v=3$，其他询问都满足 $u'=u,v'=v$。  - 可以看出，从 $4$ 到 $7$ 需要经过一条线； - 从 $6$ 到 $3$ 不需要经过直线； - 从 $5$ 到 $2$ 不需要经过直线； - 从 $4$ 到 $8$ 需要经过一条线； - 故答案分别为 $1,0,0,1$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（1 pts）：$f_i=i-1$，$s=-1$。 - Subtask 2（9 pts）：$f_i=1$，$s=-1$。 - Subtask 3（10 pts）：$n,q\leq 2\times 10^3$，$s=-1$。 - Subtask 4（20 pts）：$f_i=\left\lfloor\dfrac{i}{2}\right\rfloor$，$s=-1$。 - Subtask 5（59 pts）：$s=-1$。 - Subtask 6（1 pts）：无特殊限制。 对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5$，$1\leq q\leq 5\times 10^6$，$1\leq u,v\leq n$，$1\leq f_i<i$，$-1\leq s\leq 10^9$，且 $s=-1$ 时 $q\leq 5\times 10^5$。 **对于 $99\%$ 的数据，保证 $s=-1$。** **IO 量可能很大，请选择合适的读入输出方式。** #### 说明 [Minecraft OI Round 4](https://www.luogu.com.cn/contest/33344) B idea：ClCN solution：ClCN & \_Guoyh\_ check：\_Guoyh\_ --- 你问为什么 MCOI 里面混入了 AC6？ 很简单，因为 ClCN 不玩 MC。