Beautiful Pairs

★★★★★

3.8

4 votes

Algorithms, Hard, Square Root Decomposition

Details

Submissions

Discussion

Editorial

Problem

You live in a city that consists of $N$ restaurants. Each restaurant has a unique index between $1$ and $N$ (both inclusive) and value denoted by the array $V$ . A unique path exists between every pair of restaurants, which implies that each restaurant can be reached from every other restaurant. You are given an integer $P$ . Your task is to solve $Q$ queries of the following form:

$A \ B\ L_1\ R_1\ L_2\ R_2$

where $A$ and $B$ are the indices of two distinct restaurants and $L_1$ , $R_1$ , $L_2$ , and $R_2$ are positive integers. For each query, determine the total number of ordered pairs of restaurants $(X,Y)$ such that the following conditions hold:

$X$ lies in the unique path between the restaurants $A$ and $B$
$A$ lies in the unique path between the restaurants $X$ and $Y$
$L_1 \le (V_X \% P) \le R_1$
$L_2 \le (V_Y \% P) \le R_2$
$A,\ B,\ X,$ and $Y$ should be pairwise distinct

Input format

First line: Three space-separated integers $N$ , $Q$ , and $P$
Second line: $N$ space-separated integers with $i^{th}$ integer denoting $V_{i}$
Next $N-1$ lines: Two space-separated integers $U$ and $V$ denoting a bidirectional path from restaurant $U$ to $V$ and vice versa
Next $Q$ lines: Six space-separated integers $IN_{1}$ , $IN_{2}$ , $IN_3$ , $IN_4$ , $IN_5$ , and $IN_6$ describing one query. Let $last$ denote the answer of the previous query (if its first query then $last$ = 0). The parameters of the query can be calculated by the following conditions:
- $A=IN_{1} \oplus last$
- $B=IN_{2} \oplus last$
- $L_1=IN_{3} \oplus last$
- $R_1=IN_{4} \oplus last$
- $L_2=IN_{5} \oplus last$
- $R_2=IN_{6} \oplus last$

where ${\oplus}$ is the symbol for the bitwise XOR.

Output format

For each query, print the answer on a separate line.

Constraints

$2 \le N,Q \le 10^5$

$1 \le A, B \le N$ and $A \ne B$

$1 \le L_1,R_1,L_2,R_2,P,V_{i} \le 10^{9}$

$L_1 \le R_1\ and\ L_2 \le R_2$

Subtasks

For 10 points: $2 \le N,Q \le 100$
For 20 points: $2 \le N,Q \le 5000$
For 70 points: Original Constraints

Sample Input

11 5 20
10 5 6 10 10 10 10 10 10 10 10 
1 2
1 3
2 4
2 5
4 6
4 7
5 8
3 9
9 10
9 11
4 9 1 20 1 20
2 13 7 18 7 18
12 3 9 1 9 1
4 2 1 10 1 10
4 1 1 10 1 10

Sample Output

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

For the first query the possible pairs satisfying all the conditions are (1,6), (2,6), (3,6), (1,7), (2,7) and (3,7).

Contributers:

Salik Khwaja

Ivan Safonov