问题2520--大小接近的点对

2520: 大小接近的点对

时间限制: 1 Sec  内存限制: 256 MB
提交: 740  解决: 137
[状态] [讨论版] [提交] [命题人:]
题目描述
一天,Chika 对大小接近的点对产生了兴趣,她想搞明白这个问题的树上版本,你能帮助她吗?Chika 会给 你一棵有根树,这棵树有 n 个结点,被编号为 1 n,1 号结点是根。每个点有一个权值,i 号结点的权值为 a[i]。如果 u 是 v 的祖先结点,并且 abs(a[u]−a[v]) ≤K,那么 (u,v) 被称作一个“** 大小接近的点对 **”。 对于树上的每个结点 i,你都需要计算以其为根的子树中的“大小接近的点对”的数量。你需要知道: 
(1) abs(x) 代表 x 的绝对值。 
(2) 每个结点都是其自身的祖先结点.


输入
输入文件的第一行包含两个整数 n (1≤n≤105) 和 k (1≤k≤109),代表树中结点总数, 以及“大小接近的点对”的大小之差的上界。  
第二行包含 n 个整数,第 i 个整数是 a[i] (1≤ a[i] ≤109),代表 i 号结点的权值。 
第三行包含 n−1 个整数,第 i 个整数是 i+1 号结点的父结点。

输出
输出应该包含n行,每一行包括一个整数。第i行的整数代表以i为根的子树中的“大小接近的点对”的数量。
样例输入 Copy
7 5
2 4 4 1 4 6 4
1 2 3 1 2 3
样例输出 Copy
19
11
5
1
1
1
1
来源/分类