A2205. 逃离谷仓
编程题
提高+/省选-
知识点
题目描述
给定一颗 $n$ 个点的有根树，边有边权，节点从 $1$ 至 $n$ 编号，$1$ 号节点是这棵树的根。
再给出一个参数 $t$，对于树上的每个节点 $u$，请求出 $u$ 的子树中有多少节点满足该节点到 $u$ 的距离不大于 $t$。
再给出一个参数 $t$，对于树上的每个节点 $u$，请求出 $u$ 的子树中有多少节点满足该节点到 $u$ 的距离不大于 $t$。
输入格式
输入的第一行是两个整数，分别表示节点数 $n$ 和给出的参数 $t$。
第 $2$ 到第 $n$ 行，每行两个整数，第 $i$ 行的整数 $p_i, w_i$ 表示节点 $i$ 的父节点为 $p_i$，连结 $i$ 与 $p_i$ 的边的边权为 $w_i$。
第 $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}$。
对于全部的测试点，保证：
- $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}$。