Background

This is an operational deployment order.

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

The official name of the enemy cruiser 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 in front of Aigaion at the same time to carry out the refueling operation.

When tankers are refueling at the front of Aigaion, Aigaion’s radar detection capability will be temporarily weakened.

This is the key point.

While refueling, Aigaion’s radar is basically completely unable to 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 to take down this monster is when it is refueling.

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

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

Go get ready.

…………

Garuda team, 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 a plane, with root $1$, and the root has depth $0$.

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

For all children of a node, they are arranged from left to right in increasing order of node number. 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.

Each segment or ray has a weight.

Any two segments or rays intersect only at the tree’s nodes.

If you do not understand how this tree is drawn, you may 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 cannot pass through any point other than $u$ and $v$. Each time you pass through a segment or ray, you must pay a cost equal to its weight.

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

Input Format

Direct input would cause an extremely large 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$.

In the next $n-1$ lines, each line contains two integers, representing the parent of this node in the tree $f_i$ and the weight $w_i$ of the edge to its parent.

Next is an integer $w_1$, representing the weight of the upward ray of node $1$.

Next is a line of integers $d_u$ separated by spaces, giving the weights of the downward rays of all leaf nodes in increasing order of leaf node number (note: not from left to right in the tree).

Then, for each query, let the answer to the previous query be $\text{lastans}$. If this is the first query, then $\text{lastans}=0$. You need to first compute $(\text{read}()\oplus \text{lastans})\bmod n+1$ to get $u$, and then compute $(\text{read}()\oplus \text{lastans})\bmod n+1$ to get $v$. Here $\oplus$ denotes the XOR operation.

Output Format

Output two integers separated by two spaces, representing the XOR of all answers and the sum of all answers.

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

2 6362

Hint

idea: Sol1, solution: dengyaotriangle & Sol1 & Guoyh, code: Sol1, data: Sol1.

Constraints: For $100\%$ of the testdata, $1\leq n\leq 5\times 10^5$, $1\leq q\leq 5\times 10^6$, $1\leq f_i<i$, $1\leq w_i,w_1,d_{u}\leq 2\times 10^3$, $0\leq s\leq10^9$.

---

「Return to the sea……」

「You can rest now……」

「Rest in peace.」

Translated by ChatGPT 5