← 返回题目
题库练习 逃离谷仓
← 上一题 下一题 →

A2205 | 逃离谷仓

来源USACO / 2012
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一颗 $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
C++ 编辑器
输入
输出