树的距离
题号:NC14415
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

wyf非常喜欢树。一棵有根数树上有N个节点,1号点是他的根,每条边都有一个距离,而wyf是个爱问奇怪问题的熊孩子,他想知道对于某个点x,x为根的子树上,所有与x距离大于等于k的点与x的距离之和。

输入描述:

第一行一个正整数N

接下来N-1描述这棵树,每行两个数第i行两个数p和D表示树上有一条p到i+1长度为D的边。(p<=i)

下面一行一个正整数Q表示wyf的询问次数。

接下来Q行每行两个正整数x和k。 (1<=N,Q<=2x105,1<=D,K<=106)

输出描述:

对于每次询问x,k输出以x为根的子树上,所有与x距离大于等于k的点与x的距离之和。(若不存在这样的点,则输出应为0)
示例1

输入

复制
3
1 2
1 3
2
1 3
1 2

输出

复制
3
5