题目描述

有 $N$ 个城市，由 $N-1$ 条高速公路连接成一棵以城市 $1$ 为根的树。每条高速公路都有长度。

城市 $X$ 可以与其子树中的城市 $Y$ 开通直达航班，但要求 $X$ 与 $Y$ 之间的高速公路总长度不超过 $L$。

对于每个城市，求可以与它开通直达航班的城市数量。城市自身也计算在内。

输入格式

第一行包含两个整数 $N,L$。

接下来 $N-1$ 行，第 $i-1$ 行包含两个整数 $F_i,P_i$，表示城市 $F_i$ 是城市 $i$ 的父节点，连接两座城市的高速公路长度为 $P_i$。

输出格式

输出 $N$ 行，第 $i$ 行包含一个整数，表示城市 $i$ 可以到达的城市数量。

5 10
1 12
1 2
3 8
3 9

3
1
3
1
1

数据范围与提示

• 对于 $30\%$ 的数据，$1 \le N \le 5000$，$1 \le L \le 3000$
• 对于全部数据，$1 \le N \le 2 \times 10^5$，$1 \le L \le 10^{18}$
• $1 \le F_i < i$
• $1 \le P_i \le 10^{12}$