Turing Grandma

题目描述

Turing Grandma likes knitting wool sweaters. The $i$-th sweater she knits is represented by a weighted tree $D_i$. And you are given the pattern weighted tree $T$ with $n$ vertices numbered from $1$ to $n$.

For the current weights of $T$, the sequence of sweaters $D_0, D_1, D_2, \ldots$ is defined as follows.

The initial sweater $D_0$ consists of a single vertex.

For $k \ge 1$, Grandma uses several smaller sweaters of type $D_{k-1}$ to knit a larger sweater $D_k$ as follows:

1. She takes $n$ pairwise disjoint smaller sweaters, each being a copy of $D_{k-1}$, and numbers them from $1$ to $n$.
2. In the $i$-th smaller sweater, she chooses the vertex corresponding to the $i$-th key vertex of $D_{k-1}$.
3. For every edge connecting $a$ and $b$ with current weight $w$ in $T$, she connects the chosen vertex in the $a$-th smaller sweater and the chosen vertex in the $b$-th smaller sweater by an edge of weight $w$.
4. In the larger sweater $D_k$, the chosen vertex in the $i$-th smaller sweater becomes the $i$-th key vertex of $D_k$.

For every $1 \le i \le n$, the $i$-th key vertex of $D_0$ is defined to be this single vertex.

For a weighted tree $G$, let $\operatorname{dist}_G(u, v)$ be the sum of edge weights on the simple path between vertices $u$ and $v$.

For every positive integer $k$, define the complexity of the sweater $D_k$ as

$$\operatorname{comp}(D_k)=\sum_{\{u,v\}\subseteq V(D_k)} \operatorname{dist}_{D_k}(u,v).$$

There are $q$ queries. Before each query, the generator changes the weight of exactly one edge in $T$. The query is then answered using the current edge weights after this change.

Let $A_i$ be the answer to the $i$-th query. Since the output may be large, you only need to print

$$(A_1 \cdot 1)\operatorname{xor}(A_2 \cdot 2)\operatorname{xor}\cdots\operatorname{xor}(A_q \cdot q).$$

Here $\operatorname{xor}$ denotes bitwise xor. The multiplication by the query index is ordinary integer multiplication and is not taken modulo $998244353$.

Please pay attention to the input format.

输入格式

The first line contains four integers $n$, $q$, $K$, and $\mathit{seed}$, where $n$ ($2 \le n \le 10^6$) is the number of vertices, $q$ ($1 \le q \le 4 \cdot 10^7$) is the number of queries, $K$ ($1 \le K \le 10^{18}$) is the upper bound on query values, and $\mathit{seed}$ ($0 \le \mathit{seed} \le 2^{61}$) is the initial seed of the generator.

Each of the next $n - 1$ lines contains two integers $p_v$ and $w_v$ for $v = 2, 3, \ldots, n$, meaning that there is an edge between $v$ and $p_v$ with initial weight $w_v$, where $1 \le p_v \lt v$ and $1 \le w_v \le 100$.

There is no further input. Edge updates and query values are generated by the following code. The loop is executed for $i = 1, 2, \ldots, q$.

  
unsigned long long x = 123456789, y = 362436069, seed;  
  
unsigned long long gen() {  
    unsigned long long t;  
    x ^= x « 16;  
    x ^= x » 5;  
    x ^= x « 1;  
    t = x;  
    x = y;  
    y = seed;  
    seed = t ^ x ^ y;  
    return seed;  
}  
  
for (int i = 1; i <= q; ++i) {  
    int v = gen() % (n - 1) + 2;
    int w = gen() % 100 + 1;
    // Change the weight of the edge between v and p\_v to w.  
    long long k_i = gen() % K + 1;
    // Answer the i-th query with value k_i.  
}  

输出格式

Print $(A_1 \cdot 1)\operatorname{xor}(A_2 \cdot 2)\operatorname{xor}\cdots\operatorname{xor}(A_q \cdot q).$

样例输入 #1

2 3 2 1
1 1

样例输出 #1

842