题目描述

给出一棵 $n$ 个节点的树，结点标号从 $1$ 到 $n$ 。

定义树上两点 $a,b$ 的距离 $d(a,b)$ 是最小的非负整数 $k$ ，满足存在结点序列 $v_0,v_1,...,v_k$ ，满足 $v_0=a,v_k=b$ ，且对于 $0\leq i\leq k-1$ 有 $v_i$ 和 $v_{i+1}$ 之间在树上有一条边相连。

有 $m$ 个询问，每个询问包含参数 $p_0,d_0,p_1,d_1$ ，求：

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

输入格式

第一行一个整数 $n$ ，表示树的节点数目。

接下来一行 $n-1$ 个整数 $f_2,f_3,...,f_n$ ，依次表示 $i$ 和 $f_i$ （ $1\leq f_i\leq i-1$ ）之间有一条边。

接下来一行一个整数 $m$ ，表示询问数目。

接下来 $m$ 行依次描述所有询问：每行四个证书 $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$ ）描述一组询问。

保证 $1\leq n\leq 10^5,1\leq m\leq 10^5$ 。

输出格式

共 $m$ 行，依次回答各组询问：每行输出一行一个整数表示这组询问的答案。

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

提示

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。