「THUPC 2019」不用找的树
题目描述
给出一棵 n 个节点的树,结点标号从 1 到 n。
定义树上两点 a,b 间的距离 d(a,b) 是最小的非负整数 k,满足存在结点序列 v0,v1,…,vk,满足 v0=a,vk=b,且对于 0≤i≤k−1 有 vi 和 vi+1 之间在树上有一条边相连。
有 m 个询问,每个询问包含参数 p0,d0,p1,d1,求:
$$\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)}}$$
分别令 A={a∣d(p0,a)≤d0}、B={b∣d(p1,b)≤d1}。统计的是笛卡尔积 A×B 中的有序点对;两集合可以重叠,允许 a=b,此时贡献为 0。答案不取模。
输入格式
第一行一个整数 n,表示树的节点数目。
接下来一行 n−1 个整数 f2,f3,…,fn,依次表示 i 和 fi(1≤fi≤i−1)之间有一条边。
接下来一行一个整数 m,表示询问数目。
接下来 m 行依次描述所有询问:每行四个整数 p0,d0,p1,d1(1≤p0,p1≤n,0≤d0,d1≤n−1)描述一组询问。
保证 1≤n≤105,1≤m≤105。
输出格式
共 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