题目描述

给定一棵 $n$ 个结点的树，点的编号为 $1$ 到 $n$，$1$ 号点为根。树上第 $i$ 个点与其父亲的距离为 $d_i$。给定一个上限 $m$，与一个编号为 $u$ 的点，定义 $S(u,m)$ 为 $u$ 的子树中，与 $u$ 距离不超过 $m$ 的点的数量。

对任意点 $1\leq i\leq n$，请计算并输出 $S(i, u)$。

输入格式

• 第一行：单个整数表示 $n$；
• 第二行：单个整数表示 $m$；
• 第三行到第 $n+1$ 行：第 $i+1$ 行有两个整数 $p_i$ 与 $d_i$，
  • $p_i$ 表示 $i$ 号点的父亲编号
  • $d_i$ 表示 $i$ 号点到父亲的距离

输出格式

• 共 $n$ 行，每行一个整数，其中第 $i$ 行表示 $S(i, u)$

3
10
1 6
1 5

3
1
1

5
8
1 3
1 5
2 4
2 6

4
3
1
1
1

数据范围

• 对于 $30\%$ 的数据， $n\leq 200$；
• 对于 $60\%$ 的数据， $n\leq 5000$；
• 对于 $100\%$ 的数据， $1\leq n\leq 200,000$
• $1\leq m\leq 10^{18}$
• $1\leq d_i\leq 1,000,000,000$
• $1\leq p_i<i$