19511번 - Flight 다국어

문제

You are given a tree with $N$ vertices. The distance between two vertices is the number of edges lying on the simple path between them.

There are $Q$ queries. Each query is specified by two vertices $u$ and $v$ and an integer $d$. A pair of vertices is called good if the distance between them is not less than $d$. In each step, you can only move between a good pair of vertices. Now your task is to calculate the minimum number of steps you have to make in order to get from $u$ to $v$. If you can not reach the destination, the answer is $-1$.

A lot of queries are given to you to make this problem difficult.

입력

The first line of input contains three integers $N,ドル $Q$ and $M$: the number of vertices, the number of queries and the upper bound for $d$. (1ドル \leq N \leq 2 \cdot 10^5,ドル 1ドル \leq Q \leq 10^6,ドル 1ドル \leq M \leq 2 \cdot 10^5$).

The second line contains $N - 1$ integers $f_2,ドル $f_3,ドル $\ldots,ドル $f_N$ which mean that, for every $i$ such that 2ドル \leq i \leq N,ドル there is an edge between vertices $i$ and $f_i$ in the tree (1ドル \leq f_i < i$).

The third line contains six integers $u_1,ドル $v_1,ドル $d_1,ドル $A,ドル $B$ and $C$ (1ドル \leq u_1, v_1 \leq N,ドル 0ドル \leq d_1 < M,ドル 10ドル^4 \leq A, B, C \leq 2 \cdot 10^4$).

The first query is specified by $u_1,ドル $v_1$ and $d_1$.

The $i$-th (2ドル \leq i \leq Q$) query is specified by $u_i,ドル $v_i$ and $d_i$ which are generated by the following rules:

• $u_i = ((A \cdot u_{i - 1} + B + \mathit{ans}_{i - 1}) \bmod N) + 1,ドル
• $v_i = ((B \cdot v_{i - 1} + C + \mathit{ans}_{i - 1}) \bmod N) + 1,ドル
• $d_i = (C \cdot d_{i - 1} + A + \mathit{ans}_{i - 1}) \bmod M$.

Here, $\mathit{ans}_{k}$ is the answer for query $k$.

출력

Output the integer $$S = \sum\limits_{i = 1}^{Q} i \cdot (\mathit{ans}_i + 1)\text{.}$$

제한

힌트