#P5374. [THUPC2019] 不用找的树
[THUPC2019] 不用找的树
题目描述
给出一棵 个节点的树,结点标号从 到 。
定义树上两点 的距离 是最小的非负整数 ,满足存在结点序列 ,满足 ,且对于 有 和 之间在树上有一条边相连。
有 个询问,每个询问包含参数 ,求:
$$\sum\limits_{d(p_0,a)\leq d_0}\sum\limits_{d(p_1,b)\leq d_1}d(a,b) $$输入格式
第一行一个整数 ,表示树的节点数目。
接下来一行 个整数 ,依次表示 和 ( )之间有一条边。
接下来一行一个整数 ,表示询问数目。
接下来 行依次描述所有询问:每行四个证书 ( )描述一组询问。
保证 。
输出格式
共 行,依次回答各组询问:每行输出一行一个整数表示这组询问的答案。
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 查看。