Description

You are given 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 every $0\leq i\leq k-1$, there is an edge directly 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$, the number of nodes in the tree.

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

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

The next $m$ lines describe the 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.

Constraints: $1\leq n\leq 10^5,1\leq m\leq 10^5$.

Output Format

Output $m$ lines. For each query, output one integer on its own line, 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

Copyright Information

From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019.

Resources such as editorials can be found at https://github.com/wangyurzee7/THUPC2019.

Translated by ChatGPT 5