Background

This is a combat deployment order.

We have obtained some classified intelligence about the enemy heavy command cruiser from the National Security Bureau.

The enemy cruiser’s official name has been confirmed as P-1112 Aigaion.

In the air fleet, there is a Kottos medium cruiser responsible for electronic support, and a Gyges medium cruiser responsible for short-range air defense.

Aigaion, as the command aircraft, is responsible for everything related to cruise missiles.

After obtaining this intelligence, we can draft a plan to destroy Aigaion.

Listen carefully.

Aigaion can only receive aerial refueling at the front of its fuselage.

Multiple tankers must be simultaneously in front of Aigaion to conduct refueling operations.

When tankers refuel at Aigaion’s front, Aigaion’s radar detection ability will be temporarily weakened.

This is the key point.

When Aigaion is refueling, its radar basically cannot detect objects flying in front of it.

If you can maintain a fixed route and fly at a specific altitude, you can approach Aigaion from the air without being detected by the enemy.

So the best time for us to take down this monster is when it is refueling in the air.

Aigaion’s planned route map is also included in this intelligence.

After the briefing, we will check the route map again in the hangar.

Go get ready.

…………

Garuda Squadron, engage!

$$_{{\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\ -$$

Problem Description

A rooted tree is given on the plane, with root $1$, and the depth of the root is $0$.

For a node with depth $x$, its $y$-coordinate is $n-x+1$.

For all children of a node, they are ordered from left to right by increasing index. Each edge is a line segment connecting two points.

Each leaf node has a ray parallel to the $y$-axis and extending infinitely in the negative $y$ direction, and the root node has a ray parallel to the $y$-axis and extending infinitely in the positive $y$ direction.

Any two line segments or rays intersect only at the nodes of the tree.

If you do not understand how this tree is drawn, you can read the explanation of Sample 1.

Given $q$ pairs $(u, v)$, you now start from point $u$ and can move freely on the plane, but you are not allowed to pass through any point other than $u$ and $v$. Each time you pass through a line segment or a ray, it costs $1$.

Your goal is to move to point $v$. You need to find the minimum cost incurred during the movement.

Input Format

Direct input would cause an enormous input size, so this problem uses a special input method.

The following random number generator is given:

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;
}

The first line contains three integers $n, q, s$.

The next line contains $n-1$ integers describing the tree structure. The $i$-th number denotes the parent index $f_i$ of node $i+1$.

Then:

• If $s=-1$, then the next $q$ lines in standard input each contain two integers separated by a space, representing the query values $u'$ and $v'$. Let the answer to the previous query be $\text{lastans}$. The actual query you need to process is $u=u'\oplus \text{lastans}$ and $v=v'\oplus \text{lastans}$, where $\oplus$ denotes the XOR operation. If this is the first query, then $\text{lastans}=0$.
• Otherwise, you need to first compute $u=(\text{read}()\oplus \text{lastans})\bmod n+1$, and then compute $v=(\text{read}()\oplus \text{lastans})\bmod n+1$.

Output Format

If $s=-1$, output $q$ lines, each being the answer to the corresponding query.

If $s\geq 0$, output two integers separated by two spaces, representing the XOR of all answers and the sum of all answers, respectively.

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

Hint

For the enhanced version, see P7434.

Sample 1 Explanation

In the second query, the actual query is $u=6, v=3$. All other queries satisfy $u'=u, v'=v$.

• It can be seen that going from $4$ to $7$ requires passing through one line.
• Going from $6$ to $3$ does not require passing through any line.
• Going from $5$ to $2$ does not require passing through any line.
• Going from $4$ to $8$ requires passing through one line.
• Therefore the answers are $1, 0, 0, 1$.

Constraints

This problem uses bundled testdata.

• 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): no special constraints.

For $100\%$ of the data: $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$, and when $s=-1$, $q\leq 5\times 10^5$.

For $99\%$ of the data, it is guaranteed that $s=-1$.

The IO size may be very large. Please choose appropriate input and output methods.

Notes

Minecraft OI Round 4 B
idea: ClCN solution: ClCN & _Guoyh_ check: _Guoyh_

---

You ask why AC6 is mixed into MCOI?
Very simple: because ClCN does not play MC.

Translated by ChatGPT 5