Flight

You are given a tree of $N$ vertices.

The query is specified by two vertices $u,v$ and an integer $d$ .

This time, a pair of vertices is called good if the distance between them is not less than $d$ .

(Here, distance between two vertices means the number of edges lying on the path between them.)

In each step, you can only move between good pair of vertices.

Now your task is to calculate the minimum number of steps to reach $v$ , starting from $u$. If you can’t reach the destination, the answer is -1 for that query.

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

There are multiple test cases. The first line of the input contains an integer $T(T\leq 15 )$, the number of test cases.

Each test case consists of the following lines:

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

The second line contains $N-1$ integers $f_2,f_3,\cdots f_N$ ,representing $(i,f_i)$ is a tree edge for every $i(2\leq i\leq N,1\leq f_i < i )$.

The third line contains six integers $u_1,v_1,d_1,A,B,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,d_1$.

The $i$ -th ($2\leq i\leq Q$ ) query is specified by $u_1,v_1,d_1$ , which are generated by the following rules:

$u_i=((A\ u_{i-1} + B + ans_{i-1})\ mod\ N) + 1$
$v_i = ((B\ v_{i-1} +C +ans_{i-1})\ mod\ N)+1$
$d_i = (C\ D_{i-1} + A +ans_{i-1})\ mod\ M$

For each test case, output an integer $S = \sum_{i=1}^{Q} i\cdot (ans_i+1)$.

1
6 9 5
1 2 1 3 3
6 3 0 10865 16947 15183

55

金策工业综合大学（DPRK）

2016 Multi-University Training Contest 9