P5374 [THUPC 2019] A Tree You Do Not Need to Search

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)$$

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 $m$ lines. For each query, output one integer on its own line, which is the answer to that query.

##### Copyright Information From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2019. Resources such as editorials can be found at . Translated by ChatGPT 5