Description

Caicaizi gives you a tree with $n$ nodes, numbered from $1$ to $n$.

Define the distance $d(a,b)$ between two nodes $a,b$ on the tree as the smallest non-negative integer $k$ such that there exists a node sequence $v_0,v_1,...,v_k$ with $v_0=a,v_k=b$, and for $0\leq i\leq k-1$, there is an edge connecting $v_i$ and $v_{i+1}$ in the tree.

There are $m$ queries. Each query contains parameters $p_0,d_0,p_1,d_1$. Compute:

$$\sum\limits_{d(p_0,a)\leq d_0}\sum\limits_{d(p_1,b)\leq d_1}d(a,b)$$

Input Format

The first line contains an integer $n$, representing the number of nodes in the tree.

The next line contains $n-1$ integers $f_2,f_3,...,f_n$, which indicate that there is an edge between $i$ and $f_i$ ($1\leq f_i\leq i-1$).

The next line contains an integer $m$, representing the number of queries.

The next $m$ lines describe all queries. Each line contains four integers $p_0,d_0,p_1,d_1$ ($1\leq p_0,p_1\leq n,0\leq d_0,d_1\leq n-1$), describing one query.

Output Format

Output $m$ lines, answering the queries in order. Each line outputs one integer, which is the answer to that query.

7
1 1 2 3 5 2
5
5 1 5 0
2 0 5 0
2 2 4 5
7 2 2 4
3 2 5 4

2
3
69
57
70

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078

Constraints: for $100\%$ of the data, $1\leq n\leq 10^5$ and $1\leq m\leq 10^5$.

Translated by ChatGPT 5