#6612. 「THUPC 2019」不用找的树 / tree

内存限制:512 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: WAAutoMaton

题目描述

给出一棵 n 个节点的树,结点标号从 1 n

定义树上两点 a,b 间的距离 d\left( a,b\right) 是最小的非负整数 k ,满足存在结点序列 v_0,v_1,\dots ,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\left(p_0,a\right)\leq d_0} {\sum\limits_{d\left(p_1,b\right)\leq d_1} {d(a,b)}}

输入格式

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

接下来一行 n-1 个整数 f_2 ,f_3 ,\dots, 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 行,依次回答各组询问:每行输出一行一个整数表示这组询问的答案。

样例

样例输入 1
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
样例输出 1
2
3
69
57
70

数据范围与提示

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。

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