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