#P5374. [THUPC2019] 不用找的树

[THUPC2019] 不用找的树

题目描述

给出一棵 nn 个节点的树,结点标号从 11nn

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

mm 个询问,每个询问包含参数 p0,d0,p1,d1p_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) $$

输入格式

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

接下来一行 n1n-1 个整数 f2,f3,...,fnf_2,f_3,...,f_n ,依次表示 iifif_i1fii11\leq f_i\leq i-1 )之间有一条边。

接下来一行一个整数 mm ,表示询问数目。

接下来 mm 行依次描述所有询问:每行四个证书 p0,d0,p1,d1p_0,d_0,p_1,d_11p0,p1n,0d0,d1n11\leq p_0,p_1\leq n,0\leq d_0,d_1\leq n-1 )描述一组询问。

保证 1n105,1m1051\leq n\leq 10^5,1\leq m\leq 10^5

输出格式

mm 行,依次回答各组询问:每行输出一行一个整数表示这组询问的答案。

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 查看。