题目描述

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

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

输入格式

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

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

输出格式

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

样例

输入样例

4 5 
1 4 
2 3 
1 5

输出样例

3 
2 
1 
1

提示

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

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

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