逃离牛棚(Running Away From the Barn G)

题目描述

给定一颗 $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$ 的节点个数。

样例输入 #1

4 5
1 4
2 3
1 5

样例输出 #1

3
2
1
1

数据范围

数据规模与约定

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

• $1 \leq n \leq 2 \times 10^5$，$1 \leq t \leq 10^{18}$。
• $1 \leq p_i \lt i$，$1 \leq w_i \leq 10^{12}$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接