题目描述

给定一颗 ${n }$个点的有根树，边有边权，节点从 ${1 }$至 ${n }$编号，${1 }$号节点是这棵树的根。

再给出一个参数 ${t，}$对于树上的每个节点 ${u，}$请求出 ${u }$的子树中有多少节点满足该节点到 ${u }$的距离不大于 ${t}$。

输入格式

输入的第一行是两个整数，分别表示节点数 ${n }$和给出的参数 ${t}$。

第 ${2 }$到第 ${n }$行，每行两个整数，第 ${i }$行的整数 ${p_i, w_i, }$表示节点 ${i }$的父节点为 ${p_i ，}$连结 ${i }$与 ${p_i}$的边的边权为 ${w_i}$。

输出格式

输出 ${n }$行，每行一个整数，第 ${i }$行的整数表示 ${i }$的子树内到 ${i }$的距离不大于 ${t }$的节点个数。

样例

输入样例

4 5 
1 4 
2 3 
1 5

输出样例

3 
2 
1 
1

提示

对于全部的测试点，保证：

${1 \leq n \leq 2 \times 10^5，}$${1 \leq t \leq 10^{18}}$。

${1 \leq p_i \leq i，}$${1 \leq w_i \leq 10^{12}}$